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