cm plus 0.02 cm minus 0.02 cm

[

高速多重極展開法とツリー法 --- O(N) は O(N logN) より速いか？

牧野淳一郎
東京大学大学院総合文化研究科
東京都目黒区駒場 3-8-1
makino@grape.c.u-tokyo.ac.jp

cm plus 0.02 cm minus 0.02 cm

We present an overview for the Fast Multipole Method (FMM) and the Barnes-Hut tree method. We describe the basic algorithms as well as recent developments, such as Anderson's method of using Poisson's formula, the use of FFT, and several other optimization techniques. For many-body simulations, numerical experiments indicate that Barnes-Hut tree method is preferred over FMM by a small margin, though theoretical scaling is better for the latter.

true cm

]

• 1 はじめに
• 2 原理
• 3 それぞれの方法の歴史と現状
• 4 FMMの効率的実装
• 5 多体問題専用計算機との関係
• 6 まとめ
• References
• About this document ...