3 FMMの原理

ツリー法の原理から FMM の原理にはほんの一歩である。ツリー法では、ある 粒子への力を計算するのに、遠くの粒子からの力はまとめて計算することにし た。相互作用は対称的であるので、逆にある粒子から遠くの粒子への力をまと めて計算するということも考えられる。両方を同時にやれば、ある一群の粒子 から別の一群の粒子への力をまとめて計算することになる(図2)。このように、 受ける側もまとめてやることによって、以下に説明するようにツリー法の から へ計算量のオーダーを下げることができる。この ためにこの方法には「高速」多重極展開法という名前がついている。

 
図 2: ツリー法（上）とFMM（下）

力を受けるほうは、重力ポテンシャルのテイラー展開を求めておいて、それを 各粒子の位置で評価するという操作が必要になる。もちろん、実際にはポテン シャルは調和関数になっているので、球面調和関数で展開することで項数をテ イラー展開に比べて減らすことができる。この展開のことを、以下局所展開と 呼ぶ。

この方法は、Rokhlin と Greengard によってまず2次元の場合に提案され [8]、すぐに3次元に拡張された [9]。考え方は2次元でも3次元でも同じであるので、 例によって図は2次元で示す（図3）。ツリー法では適応的なツリー構造を扱っ たが、 FMM ではとりあえず一様なツリー構造を考える。すなわち、ツリーの レベルを k とすると、元の正方形を 個の小正方形に分割する。なお、 適応的なツリー構造の場合のアルゴリズムは例えば[4]を みられたい。ツリー法の場合と同様に、あらかじめ各セルに含まれる粒子（一 つも無いこともありえるが）が作るポテンシャルの多重極展開は準備しておく。

 
図 3: FMMの概念。もっとも濃く塗ったセルに入っている粒子への力を評価する。 自分とその回りの8個のセルからの寄与は直接計算し、さらにその回りの27個は多重 極展開を使う。その上のレベルは親セルが面倒を見る。

FMMでは、一つの粒子への力を以下のように分割する

ここで、 は直接計算する分で、自分のいるセルと、それに隣接した セルの粒子からの力である。これらには多重極展開は使えないので、直接計算 することになる。残るのが であるが、これはさらにツリーのレベル毎 に別に計算する。つまり、あるセル i に対し、(i)そのセルと同じレベルに あって、(ii)その親セルとその隣接8セルの合計9セルの子であって、(iii)問 題のセルには隣接していない、27 (=36- 9)個のセルを考える。この27個の セルに含まれる粒子が作る重力ポテンシャルの局所展開の和を、セル iの中 心で評価しておく。トップレベル（系全体）と、そのすぐ下のレベルでは、親 のレベルでは隣接していて自分のレベルでは隣接していないものは存在しない ので、計算の必要はない。

このようにして各レベルで重力場を計算しておくと、あとは粒子の位置で、そ れぞれのレベルでの局所展開を評価して合計すればいい。が、別に粒子毎に全レベ ルでの展開を評価しなくても、上のレベルの展開は一段下に移してやって（展 開の中心をシフトして）まとめておけば、粒子は全部まとめた局所展開を一度 だけ評価すればいい。この、局所展開をシフトしながら下に落していくのは、 最初に多重極展開をやはりシフトしながら上にあげていくのとちょうど対称的 な操作になる。

図4のように、4レベルのセルの中心での展開を合計する場合を考えてみる。ま ず、一番上のレベルのセルの中心での局所展開を、4つの子セルの中心に展開 中心をシフトしてそれぞれのレベルでの重力場の局所展開と足し合わせる。さ らに、それぞれの子セルで、合計した局所展開をまたそれらの4つの子セルの 中心にシフトし、またそこでの局所展開と足し合わせる。これを最下層のセル に達するまで繰り返すと、各セルの中心での、自分と自分に隣接するセルに入っ ている粒子を除いた他のすべての粒子による力の局所展開がもとまる。粒子一 つへの力は、この最下層での局所展開を粒子の位置で評価したものと、隣接セ ルの粒子からの力の合計ということになる。

 
図 4: 局所展開のシフトと加算

ここで計算量のオーダーを考えてみると、すべての操作の計算量が粒子数ま たはセルの数にしか比例していないことがわかる。セル数は粒子数に比例する ようにとれるので、結局計算量のオーダーが ということになるわけで ある。