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 , p and , and then compared the oating 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.
Possible algorithms to solve the N-body problem are the Burnes-Hut (BH), the Fast Multipole Method (FMM) and the Parallel Multipole Tree Algorithm (PMTA) REF .
A Practical Comparison of N-Body Algorithms
In Parallel Algorithms, Series in Discrete Mathematics and Theoretical Computer Science
Computer Science