天文学辞典 | 天文用語をわかりやすく解説

ツリー法

 

よみ方

つりーほう

英 語

tree-PM method

説 明

粒子間の重力相互作用を計算する方法の一つ。粒子分布を立方体を再帰的に分割する8分木構造で表現し、ある粒子からみて遠くにある粒子グループからの力を対応する適当なサイズの立方体内の粒子の重心(あるいはその粒子群がつくるポテンシャルの多重極展開)に置き換える。遠くの粒子ほど大きな立方体にすることで、粒子数を N として 1粒子当りの計算量を\log Nの桁に減らす
ことができる。現在の大規模な粒子系シミュレーションは殆ど全て、このツリー法、その周期境界への拡張であるツリーPM法や、ツリー法に類似した高速多重極法で行われている。
粒子間の重力相互作用を計算する方法の一つ。2次元の例で説明する。
粒子の分布する全空間を正方形で囲み、それを4つの小さな正方形に均等分割する。その正方形の中に粒子が指定した数(実装によるが最大で30個程度)以上ある場合はそれをさらに4分割する。これを、すべての正方形の中の粒子が指定した数より少なくなるまで繰り返す。こうして、大きな正方形が順次小さな正方形に枝分かれしていくツリー(木)構造を作る。ある正方形の中の粒子からある粒子への力は、正方形と粒子の距離が正方形のサイズより十分大きいなら正方形内の粒子の作るポテンシャルの多重極展開で置き換える。そうでなければ4つに分割した正方形 からの力の合計とする。この分割も、必要に応じて繰り返す。最小サイズの正方形まできても十分離れていない場合にはその中の粒子からの力を直接計算する。粒子分布全体からの力は上の手順で全粒子を含む正方形からの力として計算できる。粒子数 N の場合、1粒子当たりの計算量を N^2ではなく、N\log Nの桁に減らすことができる。現在の大規模な粒子系シミュレーションはほとんどすべて、このツリー法、その周期境界への拡張であるツリーPM法や、ツリー法に類似した高速多重極法で行われている。

2018年03月22日更新

関連画像

http://jun.artcompsci.org/papers/fmm_preprint/node3.html