Barnes-Hut
Barnes-HutによるN体問題の高速シミュレーションアルゴリズムの論文はNatureに掲載されています。残念ながら、大学の電子ジャーナルからアクセスしてもNatureの論文のダウンロードは有償($30)。学生さんにお願いして冊子体からコピーをとってもらうこととして、周辺の情報を調査しました。篠山くん、Appel (1985)とBarnes & Hut (1986) のコピーをお願いします。
論文
- Appel A. W.: An efficient program for many-body simulation, SIAM Journal on Scientific and Statistical Computing, Vol.6, pp.85--103, January 1985:Barnes-Hutのアルゴリズムの元となった論文。要コピー。ちなみに、Appleは関数型言語のコンパイラに関する研究の大御所。
- Barnes, J. & Hut, P., "A hierarchical O(N log N) force-calculation algorithm," 1986. Nature 324, 446.:いわゆる、Barnes-Hutの論文。
- Aarseth, S.J., Henon, M., & Wielen, R. 1974 Astr. & Ap. 37, 183.
- Barnes, J.E. 1986. In The Use of Supercomputers in Stellar Dynamics, eds. P. Hut and S. McMillan (Berlin: Springer-Verlag), p. 175.
- Barnes, J.E. 1990, "A Parallel Tree Code," J. Comp. Phys. 87, 161.
- Barnes, J.E. 1995. In The Formation of Galaxies, eds. C. Munoz-Tunon & F. Sanchez (Cambridge: Cambridge University Press), p. 399.
- Barnes, J.E. 1998. Dynamics of Galaxy Interactions, in Galaxies: Interactions and Induced Star formation, by R.C. Kennicutt, Jr., F. -- Schweizer, & J.E. Barnes, "GalaxiesInteractions and Induced Star Formation," Springer, 1996.
- Barnes, J. & Hut, P., "A hierarchical O(N log N) force-calculation algorithm," 1986. Nature 324, 446.
- Greengard, L., "Astrophysical N-body simulations: algorithms and challenges," 1990. Computers in Physics, 4, 142.
- Greengard, L. & Rokhlin, "A direct adaptive Poisson solver of arbitrary order accuracy,"V. 1987. J. Comp. Phys. 73, 325.
- Hernquist, L., "The formation of binary and multiple star systems," 1987. Ap. J. Suppl. 64, 715.
- Salmon, J.K. & Warren, M.S., "Skeletons from the treecode closet," 1994. J. Comp. Phys. 111, 136 .
- Sugimoto, D. et al., "A special-purpose computer for gravitational many-body problems," 1990. Nature 345, 33.: Grapeの杉本大一郎先生の論文みたいですね。
- 八杉さんによる並列化Barnes-Hutアルゴリズム:たしか、重力の伝搬、木の再構成をパイプライン化するアルゴリズムだったと思います。
実装されたシステム
- Joshua E. Barnesのホームページ
- Barnesによるtreecodeの解説 C言語のソースコード(treecode)に加えアルゴリズムとデータ構造の詳細が記述されている。
- アルゴリズムの概略の解説