ALCOMFT-TR-03-88

Martin Ziegler
Fast Relative Approximation of Potential Fields
Paderborn. Work package 1. November 2003.

Abstract: Multi-evaluation of the Coulomb potential induced by N particles is a central part of N-body simulations. In 3D, known subquadratic time algorithms return approximations up to given absolute precision. By combining data structures from Computational Geometry with fast polynomial arithmetic, the present work obtains approximations of prescribable relative error epsilon>0 in time \mathcalO(\tfrac1epsilonN·\operatornamepolylog N).

Postscript file: ALCOMFT-TR-03-88.ps.gz (287 kb).