多极扩展与Barnes-Hut算法的误差分析

详细分析了Barnes-Hut算法的基本原理,对引力场函数做详细的多极展开推导,对展开式的截断误差进行分析,然后从多极扩展的角度出发来分析BH算法的误差收敛情况,得出BH算法是FMA算法在空间质心点的二阶展开的特殊情况,并且进一步从理论上分析得到了“对于三维空间,BH算法在近似条件为θ<1／3^(1/2)(对于二维空间近似条件为θ<1/2^(1/2) 时)误差有界”的结论。

关于快速多极算法FMM的几点注解

详细分析快速多极算法FMM,对引力场的势函数进行了详细的多极展开和泰勒局部展开的推导过程,并在此基础上分析和推导了引力势的两种展开式的截断误差,讨论了FMM的误差收敛情况,说明了FMM的误差可由截断次数p进行控制。

BH算法的几点注记

N-Body问题的直接计算方法的时间复杂度是O(2),BH算法的时间复杂度为O(log)[1]。BH算法利用质心近似计算降低了时间复杂度,但同时也降低了计算结果的准确度。为把与判断足够远的参数(=/)密切相关的计算结果的近似准确度控制在要求的范围内,应用多极扩展和Gauss数值积分方法给出了BH算法质心近似的数学解释以及误差与参数的关系,得出BH算法是FMM算法和Gauss数值积分的一个特例,并指出Gauss积分法中隐含的正交多项式较FMM中常用的che-byshev正交多项式更与求解的问题相关。

FMM算法的并行化方法

详细分析快速多极算法FMM(Fast Multipole Method)的基本原理,并对引力场的势函数的多极展开和泰勒局部展开进行了详细的推导。给出了串行FMM算法的伪码描述,并对其进行并行化分析、处理,对FMM算法进行了并行化研究。最后,在基于MPI的群集并行计算环境下进行大量的实验并采集实验数据,对算法进行并行化性能分析,得到较好的并行加速比和较高的并行效率。