A practical comparison of N-body algorithms
A practical comparison of N-body algorithms
复制标题
N体算法的实际比较
DOI：
10.1090/dimacs/030/06
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
G. Narlikar
中科院分区：
文献类型：
--
作者：
G. Blelloch;G. Narlikar
本文对三维N体问题的三种算法--Barnes-Hut算法、Greengard的快速多极子算法(FMM)和并行多极子树算法(PMTA)进行了比较，以确定哪种算法在实际应用中表现最好。虽然FMM具有更好的渐近运行时间(对于均匀分布，它的渐近运行时间为O(N)而不是O(N Log N))，但算法更加复杂，并且在实际应用中不能立即清楚地知道在N的哪个值以上它的性能更好。我们研究了精度对变量参数p和的依赖关系，然后比较了三种算法在类似精度水平下对带电随机分布和非带电随机分布的Oating点运算计数。在高精度水平(均方根误差10？5)下，假设带电和不带电的点数分布，FMM对N>；104进行的操作次数最少。在较低的精度水平下(均方根误差10？3)，对于非电荷分布，FMM的性能甚至没有超过Barnes-Hut；N>；108。对于带电粒子分布，FMM和PMTA在低精度下都是相当的。算法用并行语言NESL实现。
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 Multi-pole 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.