ツリー法[1,2]はN個の質点間の重力相互作用を
の計算コストで計算する方法であり、宇宙論的 N体（あるい
はSPH）計算や、銀河の形成、相互作用のシミュレーションでは広く使われて
いる。計算法の原理については例えば [8]やそのなかであげた
文献を参考にしていただくとして、基本的な発想は、遠くの粒子を適当にまと
めて、それらからの重力を多重極展開におきかえて評価するというものである。
遠くにいくほどまとめ方を大きくしていけるので、粒子一つへの重力を計算す
る計算量は 
となり、全粒子への重力を計算するのに
のオーダーの計算量で済む。直接計算では計算量は 
に比例するので、粒子数が十分大きいところで ツリー法 はまともにやるのに
比べてはほとんど N に比例して速いということになる。
もちろん、
の前につく係数は決して小さくはないが、それほど高い
計算精度を要求しなれば、 N が数百程度で直接計算よりも速くなる。
さて、ツリー法は提案から 10 年以上過ぎ、銀河形成や銀河・銀河相互作用、 あるいは宇宙論などの N 体計算や SPH を使った自己重力 流体計算に広く使われるようになっている。これらの計算では、無衝突系を扱 うという性格上、計算精度をあげるためには粒子数を増やして particle noise (あるいは2体緩和)を押えることが、粒子間相互作用の精度を上げるこ とよりも重要であり、そのためにツリー法のほうが直接計算よりもよい結 果が得られるためである。
これに対して、散開星団、球状星団の熱的進化や、あるいは惑星形成のような、 2体緩和によって系が進化する過程を扱う場合には、ツリー法はほとんど使わ れていうない。これには以下のような事情があった。まず、長時間シミュレーションが必要になるために、扱える粒子数が減る。 また、計算精度も高くする必要がある。そうすると、ツリー法の計算量と直接 計算の計算量の差が小さくなるか、場合によっては逆転してしまう。このため に、また、 GRAPE[11,9] によって直接計算がかな り高速化されたということもあり、これらの系には基本的には直接計算が用い られてきた。
必ずしも一般的な事情ではないが、GRAPE を作ってきた我々の観点からはまた 以下のような問題があった。GRAPE を使ってツリー法を加速することは可能で はある[7]が、 GRAPE で計算できるのは粒子（質点）の重力場だけ である。従って、遠くの粒子をまとめる時も、それらを重心で置き換えること しかできず、近似の次数でいえばダイポールよりも上げることは出来なかった。 このために、計算精度をあげようとすると非常に急速に計算時間が増えてしま い、ツリー法を使うメリットがなくなってしまっていた。
我々は、高精度のツリー法やFMM（Fast Multipole Method, 高速多重極展 開法）のような高速計算法で精度をあげるときに必要になる高次の多重極展開 を、そのままの形ではなく粒子に戻って表現する方法（疑似粒子多重極法、 Pseudoparticle Multipole Method）を開発した。これにより、 多重極展開の評価もGRAPE を使って行なえるようになり、高精度の計算が飛躍 的に加速された。さらに、実は粒子の形で表現することで、従来よりも実装が 容易になり、任意次数のツリー法が簡単に実現出来るようになった。
以下、まずツリー法についてごく簡単に説明したあと、疑似粒子多重極法 の基本的な思想について述べ、それから数学的な定式化を与える。次に、計算 精度と計算量、計算時間についての数値実験の結果をまとめる。