A Practical Comparison of N-Body Algorithms

Guy Blelloch and Girija Narlikar.
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}