高速多重極展開法とツリー法 : 多体シミュレーションのための高速算法(<特集>数値計算)

• 牧野 淳一郎

  東京大学大学院総合文化研究科広域科学専攻広域システム科学系

書誌事項

タイトル別名

• Fast Multipole Method and Tree Method : Fast Algorithms for Many Body Simulations(<Special Topics>Numerical Computation)
• 高速多重極展開法とツリー法--多体シミュレーションのための高速算法
• コウソク タジュウキョク テンカイホウ ト ツリーホウ タタイ シミュレーショ

抄録

I overview the Fast Multipole Method (FMM) and the Barnes-Hut tree method. These algorithms evaluate mutual gravitational interaction between N particles in O(N) or O(N log N) times, respectively. I present basic algorithms as well as recent developments, such as Anderson's method of using Poisson's formula, the use of FFT, and other optimization techniques. I also summarize the current states of two algorithms. Though FMM with O(N) scaling is theoretically preferred over O(N log N) tree method, comparisons of existing implementations proved otherwise. This result is not surprizing, since the calculation cost of FMM scales as O(Np^2) where p is the order of expansion, while that of the tree method scales as O(N log Np).

収録刊行物

• 応用数理

  応用数理 8 (4), 277-287, 1998

  一般社団法人 日本応用数理学会

詳細情報

• CRID: 1390282680742256128
• NII論文ID: 110007391030
• NII書誌ID: AN10288886
• ISSN: 09172270
• ISSN: 24321982
• DOI: 10.11540/bjsiam.8.4_277
• NDL書誌ID: 4625277
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I4625277
• 本文言語コード: ja
• データソース種別:
  • JaLC
  • NDL
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可