计算机应用研究
計算機應用研究
계산궤응용연구
APPLICATION RESEARCH OF COMPUTERS
2008年
1期
42-44
,共3页
N体问题%树结构%Barnes-Hut算法%快速多极子方法%并行划分
N體問題%樹結構%Barnes-Hut算法%快速多極子方法%併行劃分
N체문제%수결구%Barnes-Hut산법%쾌속다겁자방법%병행화분
N体问题的数值模拟在每个时间步都需要计算每对粒子之间的相互作用,其复杂度为O(N2).采用树结构代码不仅减少了存储开销,而且更有利于快速计算和并行划分.Barnes-Hut算法(BHA)和快速多极子方法(FMM)都是基于树结构的快速算法.BHA可快速计算各点受到的场力,计算复杂度为O(N log N),但计算精度通常只有1%;FMM通过层次划分和位势函数的多极子展开计算各点位势,其复杂度为O(N),却能达到任意精度.数值结果表明,树结构的并行效果也很好.
N體問題的數值模擬在每箇時間步都需要計算每對粒子之間的相互作用,其複雜度為O(N2).採用樹結構代碼不僅減少瞭存儲開銷,而且更有利于快速計算和併行劃分.Barnes-Hut算法(BHA)和快速多極子方法(FMM)都是基于樹結構的快速算法.BHA可快速計算各點受到的場力,計算複雜度為O(N log N),但計算精度通常隻有1%;FMM通過層次劃分和位勢函數的多極子展開計算各點位勢,其複雜度為O(N),卻能達到任意精度.數值結果錶明,樹結構的併行效果也很好.
N체문제적수치모의재매개시간보도수요계산매대입자지간적상호작용,기복잡도위O(N2).채용수결구대마불부감소료존저개소,이차경유리우쾌속계산화병행화분.Barnes-Hut산법(BHA)화쾌속다겁자방법(FMM)도시기우수결구적쾌속산법.BHA가쾌속계산각점수도적장력,계산복잡도위O(N log N),단계산정도통상지유1%;FMM통과층차화분화위세함수적다겁자전개계산각점위세,기복잡도위O(N),각능체도임의정도.수치결과표명,수결구적병행효과야흔호.
