树结构在N体问题中的应用  

Application of tree structure in N-body problem

作　　者：王武[1] 冯仰德[1] 迟学斌[1] 

机构地区：[1]中国科学院计算机网络信息中心超级计算中心

出　　处：《计算机应用研究》2008年第1期42-44,共3页Application Research of Computers

基　　金：国家“973”计划资助项目(2005CB321702);国家自然科学基金资助项目(60533020)

摘　　要：N体问题的数值模拟在每个时间步都需要计算每对粒子之间的相互作用,其复杂度为O(N2)。采用树结构代码不仅减少了存储开销,而且更有利于快速计算和并行划分。Barnes-Hut算法(BHA)和快速多极子方法(FMM)都是基于树结构的快速算法。BHA可快速计算各点受到的场力,计算复杂度为O(NlogN),但计算精度通常只有1%;FMM通过层次划分和位势函数的多极子展开计算各点位势,其复杂度为O(N),却能达到任意精度。数值结果表明,树结构的并行效果也很好。The simulation of N-body problem was the solution of ODE with time. The calculation of force for each pair of particles per time step iteration had a complexity of O（N2 ）. Tree structure code not only reduced the storage, but also benefited the calculation and parallel partition. Barnes-Hut algorithm （BHA） and fast muhipole method （FMM） were fast methods based on tree structure. BHA could quickly calculate the force for each particle, its complexity was O（N log N）, but the accuracy was 0.01. FMM calculated the potential for each particle by hierarchical partition and muhipole expansion of potential function, its complexity was only O（N）, and could reach arbitrary accuracy. The numerical result also indicates that the tree structure has a good parallel effection.

关 键 词：N体问题 树结构 Barnes-Hut算法 快速多极子方法 并行划分 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP311.12[自动化与计算机技术—计算机科学与技术]