On the Accuracy of Poisson's Formula Based N-Body Algorithms

Abstract

We study the accuracy-cost tradeoffs of a Poisson's formula based hierarchical N-body method. The parameters that control the degree of approximation of the computational elements and the separateness of interacting elements, govern both the arithmetic complexity and the accuracy of the method. Empirical models for predicting the execution time and the accuracy of the potential and force evaluations for three-dimensional problems are presented. We demonstrate how these models can be used to minimize the execution time for a prescribed error and verify the predictions through simulations on particle systems with up to one million particles. An interesting observation is that for a given error, defining the near-field to consist of only nearest neighbor elements yields a lower computational complexity for a given error than the two-element separation recommended in the literature. We also show that the particle distribution may have a significant impact on the error.