Parallel Algorithms. Series in Discrete Mathematics and Theoretical Computer Science, Volume 30, 1997.

59k compressed postscript / PDF

**Abstract:**
This work compares three algorithms for the three dimensional N-body
problem, the Barnes-Hut algorithm, Greengard's Fast Multipole
Method(FMM), and the Parallel Multipole Tree Algorithm (PMTA) to
determine which of the algorithms performs best in practice. Although
FMM has a better asymptotic running time (O(N) instead of O(N log N) for
uniform distributions), the algorithm is more complicated and it is not
immediately clear above what values of N it performs better in practice.
We studied the dependence of accuracy on the variable parameters theta,
p and alpha, and then compared the floating point operation counts of
the three algorithms at similar levels of accuracy, for both charged and
uncharged random distributions. At a high level of accuracy (RMS-error
~= 10^-5), the FMM did the least number of operations for N > 10^4,
assuming both charged and uncharged distributions of points. At a lower
level of accuracy, (RMS-error ~= 10^-3) for uncharged distributions, the
FMM did not outperform Barnes-Hut even for N > 10^8. For charged
distributions of particles, both the FMM and PMTA were comparable at low
accuracy. The algorithms were implemented in the parallel language
NESL.

@incollection{Blelloch94, title = "A Practical Comparison of $N$-Body Algorithms", author = "Guy Blelloch and Girija Narlikar", booktitle = "Parallel Algorithms", series = "Series in Discrete Mathematics and Theoretical Computer Science", publisher="American Mathematical Society", year = 1997}