基于Barnes Hut算法的N-body问题模拟

下载PDF

导出

摘要文章详细分析了Barnes-Hut算法的原理,并采用了Barnes-Hut算法模拟了2D N-body问题。Barnes-Hut算法采用了树形结构对质点所在的空间进行分割,并利用质心对足够远的质点群进行近似,从而使时间复杂度从直接计算的O(N2)减少到了O(N lg N)。

作者牟磊

机构地区同济大学软件工程系

出处《福建电脑》 2010年第8期115-116,共2页 Journal of Fujian Computer

关键词 N-body问题 Barnes-Hut算法四叉树模拟

参考文献3

1D.Blackston and T.Suel,"-Highly Portable and EfficientImplementations of Parallel Adaptive N-Boay Methods,"vol.-,pp.-4,1997. 被引量：1
2J.Barnes and P.Hut,"-A hierarchical O(N log N)forcecalculation algorithm,"vol.-324,PP.-449,1986. 被引量：1
3王武,冯仰德,迟学斌.树结构在N体问题中的应用[J].计算机应用研究,2008(1):42-44. 被引量：9

1Wilkinson B，Allen M．并行程序设计[M]．陆鑫达，译．北京：机械工业出版社，2002：105—107．被引量：4
2GREENGARD L,ROKHLIN V.A fast algorithm for particle simulations[J].Journal of Computational Physics,1987,73(2):325-348. 被引量：1
3BARNES J,HUT P.A hierarchical O(N log N) force calculation algorithm[J].Nature,1986,324(4):446-449. 被引量：1
4APPEL A W.An efficient program for many body simulations[J].SIAM J Sci Statist Comput,1985,6(1):85-103. 被引量：1
5ALURU S,SEVILGEN F.Dynamic compressed hyper-octrees with applications to N-body problem[C]//Proc of Foundations of Software Technology and Theoretical Comp Sci.1999:21-33. 被引量：1
6HARIHARAN B,ALURU S.Efficient parallel algorithms and software for compressed octrees with applications to hierarchical methods[J].Parallel Computing,2005,31(3-4):311-331. 被引量：1
7HU Y,JONSSON S L,TENG S H.A data-parallel adaptive N-body method[C]//Proc of the 8th SIAM Conference on Parallel Processing for Scientific Computing.Minneapolis:SIAM Press,1997:19-33. 被引量：1

1曹小林,莫则尧,刘旭,徐小文,张爱清.基于JASMIN框架的快速多极子并行解法器[J].中国科学：信息科学,2010,40(9):1187-1196. 被引量：1
2陈绍平,章社生.N体问题解析函数近似计算[J].数值计算与计算机应用,2011,32(2):143-147. 被引量：2
3黄丽霞,李俊红,刘立国,柳香.基于FPGA的可控ARM异常表设计实现[J].计算机工程与设计,2011,32(12):4010-4014.
4刘超,章社生,吴永红.多区域N体问题解析函数的近似计算[J].长江大学学报（自科版）（上旬）,2013,10(2):4-6.
5李梦玉,章社生.稠密稀疏N体问题解析函数近似计算[J].数学的实践与认识,2013,43(9):149-156. 被引量：2
6王武,王舒扬,姜金荣,孟虹松.快速多极子方法在申威众核处理器上的实现和优化[J].计算机工程与科学,2019,41(7):1161-1167. 被引量：3
7丁磊,王武,姜金荣,赵莲.基于Charm++的并行FMM实现[J].数据与计算发展前沿,2020,2(3):101-112.
8韩承磊,梁建国,傅游,叶雨曦,花嵘,李倩倩.神威·太湖之光平台上宇宙N体模拟中FMM的并行优化[J].山东科技大学学报（自然科学版）,2024,43(3):105-113.

1赖国明,杨圣云,袁德辉.用莫顿序对BH算法的改进[J].韩山师范学院学报,2006,27(6):19-23.
2徐鹏,魏紫.N-Body问题在CUDA平台上并行实现研究[J].科技信息,2009(27):62-62.
3王小伟,郭力,杨章远.N-body算法及其并行化[J].计算机与应用化学,2003,20(1):195-200. 被引量：7
4蒋彬.Kindle Fire vs.Nook Tablet:应该选择谁?[J].微电脑世界,2012(2):26-27.
5杨圣云,赖国明,霍红卫.BH算法的几点注记[J].计算机工程与设计,2006,27(16):2979-2981. 被引量：2
6王伟,曾栩鸿,王福焕,傅丽丽,曾国荪.并行时空处理模型下的快速N-body算法[J].计算机科学与探索,2011,5(11):1006-1013. 被引量：3
7唐振,张倬,柴亚辉,徐炜民.FMM算法在Cell/B.E.处理器上实现的分析与验证[J].计算机工程与科学,2011,33(8):79-83. 被引量：1
8赖国明,杨圣云,刘小跃.Particle-Particle算法并行化及改进[J].韩山师范学院学报,2005,26(6):49-53.
9李颖华.分层结构移动IP的路由研究[J].微计算机应用,2003,24(4):204-209. 被引量：2
10祝永志,王喜燕.一种基于大同步并行编程模式的N体问题的优化实现[J].电子技术（上海）,2015,0(2):28-32.

福建电脑

2010年第8期

内容加载中请稍等...