| N-体仿真中的分层树形算法 |
| |
| 引用本文： | 初学导,薛国良,陈梅.N-体仿真中的分层树形算法[J].曲阜师范大学学报,2003,29(2):4-12. |
| |
| 作者姓名： | 初学导 薛国良 陈梅 |
| |
| 作者单位： | [1]曲阜师范大学自动化研究所，山东省曲阜市 273165 [2]佛梦特大学计算机科学系，VT05405，美国 |
| |
| 基金项目： | 国家自然科学基金资助项目 ( 6 0 1740 42 )，theUSArmyResearchOfficegrantDAAH0 4-96 10 2 33andbytheNationalScienceFoundationGrantsASC-940 92 85andOSR-935 0 5 40 |
| |
| 摘 要： | 考虑两种情况：在3维空间中给出n个质点，计算每一粒子施加在其它粒子上的力，成对的相互作用可能有万有引力或者Lennard—Jones．上述两种情况的力，当两粒子间的距离达到无限大时消失．既然n个质点，两两相互作用共有n(n—1)]／2对，直接算法对力的估算所需时间为0(n^2)．这对天文中的仿真所用时间是非常大的．该文提出了一种O(log n)算法，使用n／log n处理器CREW PRAM来计算n体仿真中的场．这种最优并行算法的关键是利用一个相同的非递归自上而下的过程来代替一个递归的自上而下的计算过程．这种相似的算法对力场计算也产生了一个新的O(n)时间序列算法．
|
| 关 键 词： | N—体仿真 分层树形算法 力场评估 cost最优算法 时间序列算法 最优并行算法 |
| 文章编号： | 1001-5337(2003)02-0004-09 |
HIERARCHICAL TREE ALGORITHMS FOR FORCE COMPUTATION IN N-BODY SIMULATIONS |
| |
| Abstract: | 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. |
| |
| Keywords: | spatial tree algorithms force field evaluation N-body simulations PRAM cost optimal algorithms |
| 本文献已被 CNKI 维普 等数据库收录！ |
