N-体仿真中的分层树形算法

HIERARCHICAL TREE ALGORITHMS FOR FORCE COMPUTATION IN N-BODY SIMULATIONS

考虑两种情况 :在 3维空间中给出n个质点 ,计算每一粒子施加在其它粒子上的力 ,成对的相互作用可能有万有引力或者Lennard_Jones.上述两种情况的力 ,当两粒子间的距离达到无限大时消失 .既然n个质点 ,两两相互作用共有 [n(n - 1) ]/ 2对 ,直接算法对力的估算所需时间为O(n2 ) .这对天文中的仿真所用时间是非常大的 .该文提出了一种O(logn)算法 ,使用n/logn处理器CREWPRAM来计算n体仿真中的场 .这种最优并行算法的关键是利用一个相同的非递归自上而下的过程来代替一个递归的自上而下的计算过程 .这种相似的算法对力场计算也产生了一个新的O(n)时间序列算法 .

The following field computation problem is considered: given a cluster of n particles in 3-dimensional space, compute the force exerted on each particle by the other particles. Depending on different application, the pairwise interaction could be either gravitational or Lennard-Jones. In both cases, the force between two particles vanishes as the distance between them approaches to infinity. Since there are [n(n-1)]/2 pairs, direct method requires O(n2) times for force-evaluation. In this paper, an algorithm is presented, which computes the force field in O(log n) time using an n/log n processor CREW PRAM. A key to this optimal parallel algorithm is to replace a recursive top-down force calculation procedure of Appel by an equivalent non-recursive bottom-up procedure.