作　　者： ; ; ;

机构地区： 韩山师范学院数学与信息技术学院

出　　处： 《计算机工程与设计》 2006年第16期2979-2981,共3页

摘　　要： N-Body问题的直接计算方法的时间复杂度是O(2),BH算法的时间复杂度为O(log)[1]。BH算法利用质心近似计算降低了时间复杂度,但同时也降低了计算结果的准确度。为把与判断足够远的参数(=/)密切相关的计算结果的近似准确度控制在要求的范围内,应用多极扩展和Gauss数值积分方法给出了BH算法质心近似的数学解释以及误差与参数的关系,得出BH算法是FMM算法和Gauss数值积分的一个特例,并指出Gauss积分法中隐含的正交多项式较FMM中常用的che-byshev正交多项式更与求解的问题相关。 N-body problem is modelled numerially by direct integration in which the computation needed increases as n^2, the number of oprations of BH alogrithm that calculates the force on n bodies grows only as nlogn . BH alogrithm obtains the time complexity of nlogn 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 chebyshev orthogoanl polynimoals used by FMM.

关 键 词： 仿真 算法 多极扩展 积分法

领　　域： [自动化与计算机技术] [自动化与计算机技术]