BH算法的几点注记

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

Comments on BH algorithm

N-body problem is modelled numerially by direct integration in which the computation needed increases as 2 , the number of oprations of BH alogrithm that calculates the force on n bodies grows only as nlogn [1] . BH alogrithm obtains the time complexity of log by the mass centre approximation that reduces the accuracy of the model. By analyzing BH algorithm with multipole expansion and Gauss quadrature methods to get relation of parameter and computation accuracy, it details the mass centre approximation used by BH algorithm, upper bound of parameter and errors , shows that FMM and the Gauss quadrature method generalize BH alogrithm, presents that orthogoanl polynimoals implied by the Gauss quadrature method bring better approximation to questions be sloved than che- byshev orthogoanl polynimoals used by FMM.