A Practical Comparison of N-Body Algorithms

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