ツリー法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/07/07 07:11 UTC 版)
「N体シミュレーション」の記事における「ツリー法」の解説
ツリー構築のアニメーション。 Barnes & Hut (1986) により提案された、粒子分布をツリー構造という形で保持することにより重力相互作用の計算を O ( N ln N ) {\displaystyle {\mathcal {O}}(N\ln N)} で行うアルゴリズムは現在 Barnes & Hut のツリー法として広く用いられている。これは計算領域を表す立方体を階層的により小さな立方体に分割し、最終的に各立方体がひとつ以下の粒子しか含まないようにすることにより、粒子分布の情報をツリーとして保持するものである。ツリーの深さは O ( ln N ) {\displaystyle {\mathcal {O}}(\ln N)} であるため、ツリーの構成に要する計算量は O ( N ln N ) {\displaystyle {\mathcal {O}}(N\ln N)} である。 ある粒子に作用する重力を計算する際には、遠方の粒子群からの寄与をまとめて計算することによりコストを削減する。この際に各立方体の重心および質量を用いるが、計算の精度を上げるために四重極モーメントなどを用いる場合もある。 なお近くの粒子からの重力はツリー法で、遠方の粒子からの寄与は PM 法で計算する複合的な手法のことを tree-PM 法と呼ぶ。
※この「ツリー法」の解説は、「N体シミュレーション」の解説の一部です。
「ツリー法」を含む「N体シミュレーション」の記事については、「N体シミュレーション」の概要を参照ください。
- ツリー法のページへのリンク
