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

• 作者: 冯仰德 王武 迟学斌
• 来源期刊: 计算机应用研究
• 关键词: N体问题 树结构 Barnes-Hut算法 快速多极子方法 并行划分
• 年，卷（期）: 2008,（1）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 42-44
• 页数: 3页
• 分类号: TP301.6|TP311.12
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2008.01.010

摘要

N体问题的数值模拟在每个时间步都需要计算每对粒子之间的相互作用,其复杂度为O(N2).采用树结构代码不仅减少了存储开销,而且更有利于快速计算和并行划分.Barnes-Hut算法(BHA)和快速多极子方法(FMM)都是基于树结构的快速算法.BHA可快速计算各点受到的场力,计算复杂度为O(N log N),但计算精度通常只有1%;FMM通过层次划分和位势函数的多极子展开计算各点位势,其复杂度为O(N),却能达到任意精度.数值结果表明,树结构的并行效果也很好.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	迟学斌		10	83	6.0	9.0
2	冯仰德		1	11	1.0	1.0