FMM とツリー法のどちらも、まだ10年少々の歴史しかない新しい方法である。 しかし、特に 90年代に入ってから急速に研究が進み、すでに簡単に述べたよ うに応用分野も広まりつつある。基本的な考え方は、遠くとの相互作用はまと めるという単純なものなので、重力・クーロン相互作用に限らず非常にさまざ まな応用がありえるわけである。
ここでは、特に筆者の専門である重力多体系の観点から過去の歴史を簡単に振 り返ってみたい。
ツリー法を初めて実現したのは、プリンストン大学の学部生 A. Appel であっ
た[2]。これは 1985 年になるまで公表論文にはならなかった。彼の
方法は、ツリーを最近接粒子をまとめていくことによってボトムアップに構成
していくものであり、現在広く使われている8分木をつかうものではなかった。
8分木を使うツリー法を提案したのは当時プリンストン高等研究所にいた
J. E. Barnes と P. Hut である[3]。この方法に基づいて、
その後の数年間にベクトル型スーパーコンピュータへの効率的な実装について
の研究と分散メモリ型計算機への実装の研究が精力的に進められ、銀河や銀河
団、あるいは宇宙の大規模構造などの形成、進化のシミュレーションに広く使
われるようになった[5]。特に分散メモリの超並列計算機で
は、 
を越えるような粒子数のシミュレーションが可能になってきてい
る。
このように広く使われることになった理由の一つは、実装が比較的簡単であっ たことである。ツリー法の実装のほとんどは、4重極モーメントまでしか扱 わない。このため、多重極展開や球面調和関数といってもそれほど面倒な 計算式が出てくるわけではない。高い計算精度が必要であれば、離れたセルも ある程度まで分割して相互作用を計算する。もちろん、非常に高い計算精度が 必要になれば、より高次のモーメントをとり入れた方が計算量が減る。しかし、 天文学の応用の多くでは、粒子数が有限であることからくる particle noise で計算精度がきまっているので、相互作用の計算精度をあげるよりも、計算精 度を下げても粒子数を増やしたほうがよりよい結果が得られるのである。この ために、かなり広い応用で、4重極モーメントよりも精度をあげることには意 味がない。
このように、理論的にも実験的にも複雑なことをして精度をあげる必要がなかっ たために、ベクトル化や並列化、特に適応的な木構造の実現やロードバランシ ングなどに努力が傾注されてきた。これらの努力により高速で実用的なプログ ラムが利用可能になってきている。
FMM はツリー法とほぼ同時期にイェール大学の Greengard と Rokhlin により
提案された[1][6]。これは多重極展開と局所展
開をまともに使うものであった。その後、計算法の改良について非常に多様な
提案がなされてきた。例えば多重極展開から局所展開への変換については、
FFTを使って高速化する方法[7]や、一旦座標系を回転し、シ
フトの方向に z 軸をもってくることで計算量を 
に減らす方法
[8]などが提案されている。この他にも最近 Greengard
らによって提案された新しい方法[9]もある。これらを
使うことで、理論的な計算コストは 
よりも若干小さくなっている。
しかし、このような多様な提案があるということは、逆にいえばまだ決定版と
いうべきものはなく、多数の改善案が提案されているがそれらのうち一つが他
のものよりも圧倒的によいというわけではないということでもある。さらに、
このような方法は一般に高い精度を要求する場合にしか改善につながらない。
実際、適応的な木構造の場合にツリー法とFMMの計算速度を比較した研究
[10]では、比較的精度が低い（ポテンシャルの相対精度
が 
程度）場合、FMMはツリー法に比べて有意に遅いという結果になっ
ている。このために、現在のところ天文シミュレーションにおいては FMM は
全く使われていない。
一様に近い分布の場合については、高い計算精度や空間分解能が必要でなけれ
ば古典的な PM法[11]（particle-mesh 法）のほうが圧倒
的に効率がよく、多くの場合に必要となる周期境界条件との相性もよい。また、
高い精度が必要な場合は、Ewald 法やP
M法[11]（これ
は最近は Particle-Mesh Ewald とよばれることもあるが、本質的には同じも
のである）との優劣が問題になる。実験的には P
M法のほうが優勢である
ようである[12]。
なお、周期境界をおかない場合には FMM のほうが FFT に
基づく方法よりも有利になりうることはいうまでもない。また、2次元の場合
には3次元に比べて FMM の計算量は大きく減り、 FMM は実用性の高い方法と
なる。これは、多重極展開の項数が 
から p に減るだけでなく、幾何
学の違いのためにセル間相互作用の数が減るためである。3次元の場合は一つ
のセルが 
個のセルと相互作用するが、2次元の場合は
個であり、7倍計算量が違うことになる。
なお、後者の幾何学の違いは、空間が3(2)次元であっても実際に計算する領域 は2(1)次元である境界要素法の場合にも有利に働くことを注意しておきたい。 このために、FMMやツリー法は境界要素法には特に有効である。