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

• 作者: 初学导 薛国良 陈梅
• 来源期刊: 曲阜师范大学学报(自然科学版)
• 学科: 工学
• 关键词: 空间树形算法 力场评估 N-体仿真 PRAM cost最优算法
• 年，卷（期）: 2003,（2）
• 页码范围: 4-12
• 页数: 9页
• 分类号: TP301.6
• 字数: 7185字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-5337.2003.02.002

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	初学导	曲阜师范大学自动化研究所	11	51	3.0	7.0
2	陈梅	曲阜师范大学自动化研究所	22	47	4.0	5.0