ツリー法と FMM の違いはそれほど大きなものではない。ツリー法では、ある
粒子への力を計算するのに、遠くの粒子からの力はまとめて計算することにし
た。相互作用は対称的であるので、逆にある粒子から遠くの粒子への力をまと
めて計算するということも考えられる。両方を同時にやれば、ある一群の粒子
から別の一群の粒子への力をまとめて計算することになる(図
3)。このように、受ける側もまとめてやることによって、
以下に説明するようにツリー法の 
から 
へ計算量のオー
ダーを下げることができる。このためにこの方法には「高速」多重極展開法と
いう名前がついている。
まとめて評価するというのは実際にはどういうことかというと、セルの中心で の重力ポテンシャルのテイラー展開を求めておいて、その展開を各粒子の位置 であらためて評価するということになる。もちろん、実際にはポテンシャルは 調和関数になっているので、球面調和関数で展開することで項数をテイラー展 開に比べて減らすことができる。この展開のことを、以下局所展開と呼ぶ。
この方法は、Rokhlin と Greengard によってまず2次元の場合に提案され [12]、すぐに3次元に拡張された [11]。考え方は2次元でも3次元でも同じであるので、 例によって図は2次元で示す（図4）。ツリー法では適応的なツリー 構造を扱ったが、ここではとりあえず一様なツリー構造を考える。適応的なツ リーでも話はほぼ同様であるが、アルゴリズムがすこし面倒になる [7]。
図 4: FMMの概念。もっとも濃く塗ったセルに入っている粒子への力を評価する。
自分とその回りの8個のセルからの寄与は直接計算し、さらにその回りの27個は多重
極展開を使う。その上のレベルは親セルが面倒を見る。
一様なツリーの場合、ツリーのレベルを k とすると、元の正方形は
個
の小正方形に分割されている。ツリー法の場合と同様に、あらかじめ各セルに
含まれる粒子（一つも無いこともありえるが）が作るポテンシャルの多重極展
開は準備しておく。
FMMでは、一つの粒子への力を以下のように分割する
ここで、 
は直接計算する分で、自分のいるセルと、それに隣接した
セルの粒子からの力である。これらには多重極展開は使えないので、直接計算
することになる。残るのが 
であるが、これは多重極展開で計算する。
具体的には、まずツリーのレベル毎
に別に計算する。つまり、あるセル i に対し、(i)そのセルと同じレベルに
あって、(ii)その親セルとその隣接8セルの合計9セルの子であって、(iii)問
題のセルには隣接していない、27 (=36- 9)個のセルを考える。この27個の
セルに含まれる粒子が作る重力ポテンシャルの局所展開の和を、セル iの中
心で評価しておく。トップレベル（系全体）と、そのすぐ下のレベルでは、親
のレベルでは隣接していて自分のレベルでは隣接していないものは存在しない
ので、計算の必要はない。
なお、3次元では 27個 ではなく 189 個になる。さらに細かいことをいえば、図 4 では1つおいた先はもう多重極展開をつかってよいことにして いるが、これでは多重極展開と局所展開の収束条件ぎりぎりであってあまり精 度が良くない。2つおいた先をとることにすると、 189個が 875 個に増える。 もっとも、この 875 個というのはあまりに多いし、不要に精度が高くなって いるところもあるので、収束判定をこまめに見て1つ上のレベルのセルの展開 をつかっていいところはそれで済まそうといった細かい調節も行なわれている。
このようにして各レベルで重力場を計算しておくと、あとは粒子の位置で、そ れぞれのレベルでの局所展開を評価して合計すればいい。が、別に粒子毎に全レベ ルでの展開を評価しなくても、上のレベルの展開は一段下に移してやって（展 開の中心をシフトして）まとめておけば、粒子は全部まとめた局所展開を一度 だけ評価すればいい。この、局所展開をシフトしながら下に落していくのは、 最初に多重極展開をやはりシフトしながら上にあげていくのとちょうど対称的 な操作になる。
図5のように、4レベルのセルの中心での展開を合計する場合を考えてみる。ま ず、一番上のレベルのセルの中心での局所展開を、4つの子セルの中心に展開 中心をシフトしてそれぞれのレベルでの重力場の局所展開と足し合わせる。さ らに、それぞれの子セルで、合計した局所展開をまたそれらの4つの子セルの 中心にシフトし、またそこでの局所展開と足し合わせる。これを最下層のセル に達するまで繰り返すと、各セルの中心での、自分と自分に隣接するセルに入っ ている粒子を除いた他のすべての粒子による力の局所展開がもとまる。粒子一 つへの力は、この最下層での局所展開を粒子の位置で評価したものと、隣接セ ルの粒子からの力の合計ということになる。
ここで計算量のオーダーを考えてみると、すべての操作の計算量が粒子数ま
たはセルの数にしか比例していないことがわかる。セル数は粒子数に比例する
ようにとれるので、結局計算量のオーダーが 
ということになるわけで
ある。
ただし、ここで注意して欲しいことは、 FMM の場合セルの操作（多重極展開
から局所展開への変換とか、それらの中心のシフト）の計算量は展開の最高次
数を p として 
のオーダーになるということである。これは、展開係
数が 
個あり、さらに展開を変換する行列が密行列になるからである。
したがって、あまりなにも考えないでプログラムを書くと、計算量は
になってしまう。これに対してツリー法の場合には、子セルの多重極展開を
シフトして親セルの展開を作っていくところは 
であるが、もっとも
計算量の多い各粒子に力を及ぼすセルの多重極展開を評価するところは
にしかならない。
こう書くと、一見ツリーのほうが得なようにも見えるが、実は FMM の計算量
は 
に下げることが出来る。すなわち、最初に空間をセルに分割してツ
リー構造を作る時に、粒子 1 個まで分割しないで 
個（のオーダー）の
粒子が入っているところで止めてしまうのである。こうすればセルの総数が
個になるので、セルに関係する計算量は 
で済む。もちろん、
そのかわり粒子間相互作用を直接計算する分の計算量がもともと p に依存
しなかったのが 
になる。つまり、近傍を直接計算する分を増やして、
多重極展開で計算する分の計算量が等しくなるようにツリーの深さを最適化す
ることで、計算量を
から 
に減らせるわけである。
というわけで、ツリーと FMM の計算量の違いはあまり大きくなく、理論的に どちらが優れているというのは難しい。以下では、実験的な比較や、高速化の ためのいくつかの手法を見ていくことにする。
