2 ツリー法の原理

計算したいものは要するに以下のような常微分方程式系の右辺である。

ここで Nは粒子の数、 , はそれぞれ粒子 iの位置、質量 であり、 G は重力定数である。

右辺を評価するもっとも単純な方法は、右辺をそのまま力任せに計算すること である。粒子数が数百程度であれば、この方法（単に直接計算という）よりも 速くするのは難しい。しかし、直接計算では で計算量が増えていく ので、粒子数がある程度大きくなると直接計算は現実的ではなくなる。 計算量を減らすには、重力を及ぼす遠くの粒子を適当にまとめることが考えら れる。まとめておいて多重極展開を作っておけば、精度は必要に応じてあげら れるわけである。これがツリー法の基本的な考えである。

 
図 1: ツリー法の基本的アイディア。

粒子がある空間を分割することで多重極展開や球面調和関 数展開を使えるようにする。もっとも簡単に、空間を規則的な格子で分割した 場合を考えてみると、粒子は、自分と、自分に隣接するセルに入っている粒子 からの力は直接計算し、それ以外のセルからの力は多重極展開で計算すること になる。粒子数を N、 格子のセルの数を n とすれば、計算量は の程度となり、最適な n をとれば となる。

このやり方で無駄なところは、自分から見て非常に遠くにある粒子も近くにあ るものも全部同じ大きさのセルにわけていることである。計算精度のことを考 えるなら、遠くにいくほどセルが大きくなってよい。これを実現するために、 正方形（3次元なら立方体）を再帰的に分割していくことでツリー構造を作る。 ある粒子への力を計算するには、トップレベルからツリーを降りていって、大 きさに比べて十分遠い、つまり誤差が小さくなったとみなせるところで止めれ ばよい。十分遠いかどうかの判定には、通常は 見込み角と呼ばれる量

を使う。ここで r はセルの中心から力を評価する粒子ま での距離、 l はセルの一辺の長さである。

ここで、計算量と計算精度の間の関係が原理的にはどのようなものになるかを 簡単に述べる。細かく考えるといろいろややこしいので、とりあえず一つのセ ルからの力の誤差について考えよう。展開次数を pとすれば、あるセルから の力の相対誤差は

の程度になるはずである。ここで は で規格化し た p+1 次の多重極展開の係数の値から決まる定数である。規格化したので には上限があり、上の式からツリー法の誤差限界を与えることがで きる。

さて、計算量の方はどうなるかといえば、極めて大雑把には

で与えられるはずである。ここで、 に比例するのは、 に比例してセルが小さくなるのと、3次元なのでセルの大きさの3乗に反比例し てセルの数が増えるからである。また、多重極展開の係数の数が なので、 1つのセルからの力の計算量はに比例する。

ここで がpによらな いとかpが大きいとか仮定すれば、計算精度を決めた時に計算量がもっとも 小さくなる の値は、計算精度に無関係に となる。 つまり、精度をあげるためには次数 p をあげていくの が有効であり、見込み角を変えることで精度を調整しようとするのは計算量か ら見ると損になるのである。

しかし、現在広く使われているツリー法の実装は、p=2の固定のもの がほとんどである。また、 GRAPE 上でのツリー法の実装は、GRAPE が 計算するのが質点からの重力であるために原理的にp=1 しか扱えない。この ために、精度をあげるのは困難であったわけである。