next up previous
Next: 5 FMMの実装と高速化 Up: 高速多重極展開法とツリー法---多体シミュレーションのための高速算 法 Fast multipole Previous: 3 FMMの原理

4 他の方法との関係

さて、粒子間相互作用を高速に計算する方法は、ツリー法や FMM の他にもい ろいろある。ここでは、それらとの関係や、適切な応用について簡単に触れて おこう。

多数の粒子が作るポテンシャル場を高速に計算する方法としてもっとも広く使 われているのは、空間格子を切って FFT を使う PM法 [10](particle-mesh 法)であろう。これはほかの方 法に比べて圧倒的に高速であり、計算精度や空間分解能がそれほど高い必要が ないときには最適である。

フーリエ変換を使いつつ精度や分解能を上げる方法としては、Ewald 法や PM[10]がある。どちらも近くは直接計算、遠くは フーリエ空間で計算する。違いはフーリエ変換に FFT を使うかどうかである。 Ewald では FFT を使わないので、計算量は増えるが離散化誤差がなくなる。 これらの方法の問題点は、粒子分布が一様からずれると急速に計算量が増える ことと、周期境界条件を置かない場合には計算が面倒になることである。

これに対し、ツリー法や FMM の場合には、適応的なツリー構造を扱うプログ ラムを実現することは比較的容易であり、粒子分布の性質が悪くてもそれほど 計算量が増えない。計算法自体に、ツリーが一様かどうかに依存するところが ないためである。これはこれらの方法の大きな特徴である。なお、FFTを使う 方法とは逆に、周期境界の場合の扱いは面倒になる[13]。



Jun Makino
Tue Sep 1 21:46:06 JST 1998