Characterization of the accuracy of the fast multipole method in particle simulations
Characterization of the accuracy of the fast multipole method in particle simulations
复制标题
DOI：
10.1002/nme.2611
复制
发表时间：
2009-09-24
影响因子：
2.9
通讯作者：
Barba, L. A.
中科院分区：
文献类型：
--
作者：
Cruz, Felipe A.;Barba, L. A.
快速多极子方法(FMM)是一种快速求和算法，能够加速N-体问题的成对相互作用计算，对于N个粒子，算法复杂度从O(N-2)到O(N)。该算法极大地提高了粒子模拟在许多应用领域的能力，如静电学、流体力学的粒子公式等。尽管有关这一主题的文献提供了FMM近似的理论误差界，但在一系列计算实验中测量的误差报告并不多，这些实验表征了该方法与用户可用不同参数的关系的准确性。我们已经进行了这样的实验研究，并总结了用FMM算法对二维涡粒子方法进行的大约1500次计算的结果。除了对最大误差进行更标准的诊断外，我们还提供了误差空间分布的图示，提供了影响整体近似精度的所有因素的直观证据：多极展开、局部展开、分层空间分解(相互作用列表、局域、远域)。对于希望将FMM加速整合到他们的应用程序代码中的任何研究人员来说，本演示文稿都是一种贡献，因为它有助于理解在哪里获得或降低了准确性。版权所有(C)2009 John Wiley&Sons，Ltd.
The fast multipole method (FMM) is a fast summation algorithm capable of accelerating pairwise interaction calculations, known as N-body problems, from an algorithmic complexity of O(N-2) to O(N) for N particles. The algorithm has brought a dramatic increase in the capability of particle simulations in many application areas, such as electrostatics, particle formulations of fluid mechanics, and others. Although the literature on the subject provides theoretical error bounds for the FMM approximation, there are not many reports on the measured errors in a suite of computational experiments that characterize the accuracy of the method in relation with the different parameters available to the user. We have performed such an experimental investigation, and summarized the results of about 1500 calculations using the FMM algorithm, applied to the 2D vortex particle method. In addition to the more standard diagnostic of the maximum error, we supply illustrations of the spatial distribution of the errors, offering visual evidence of all the contributing factors to the overall approximation accuracy: multipole expansion, local expansion, hierarchical spatial decomposition (interaction lists, local domain, far domain). This presentation is a contribution to any researcher wishing to incorporate the FMM acceleration to their application code, as it aids in understanding where accuracy is gained or compromised. Copyright (C) 2009 John Wiley & Sons, Ltd.