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