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

Application of tree structure in N-body problem

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.