next up previous
Next: 6 計算速度の例 Up: 高速多重極展開法とツリー法---多体シミュレーションのための高速算 法 Fast multipole Previous: 4 他の方法との関係

5 FMMの実装と高速化

 

5.1 アンダーソンの方法

FMM を実装する上での大きな問題の一つは、定式化、特に球面調和関数のシフ トや多重極展開から局所展開への変換が複雑であり、プログラムの開発 や高速化が難しいということであった。Anderson [1]はこの 困難を解決する画期的な方法を提案した。この方法を使うとプロ グラムが簡単になるだけでなく実行速度の観点からもメリットがあるという結 果が得られている[5]。以下、この方法を簡単に紹介し よう。

基本的なアイディアは、球面調和関数の展開係数をデータとして使う代わりに、 球面でのポテンシャルの値そのものを使おうというものである。半径 a の球の 中の粒子が外に及ぼすポテンシャルは、球の表面でのポテンシャルの値がわかっ ていればラプ ラス方程式の境界値問題を解けば与えられる。解はポア ソンの公式を使って以下のように書ける

ここで n次ルジャンドル関数である。この積分を、球面上で の適当な標本点を使った数値積分に置き換える。2次元であれば、円を等分割 すればいいが、3次元では点のとり方に工夫がいる。また、エリアシングによ る誤差を防ぐために点数に応じて中の無限和を適当なところで打ち切る必要が ある。

子セルの外の多重極展開をその一つ上のセルでのそれに変換するには、上の式 に従って親セルを含む球面上でのポテンシャルを求めればいい。また、局所展 開も、 での展開が rでの展開に変わるだけで上と同じ式である。さら に、多重極展開を局所展開に変換するには、上の式をつかって局所展開す る球面上でポテンシャルを評価するればよい。つまり、上の式だけで、 FMM に必要な数学がすべて表現されていることになる。

5.2 直接計算とのトレードオフ

 

多重極展開を局所展開に変換する部分の計算コストは非常に大きい。展開次数 を p とすると3次元ではこれが に比例し、 p を大きくすると計 算量のほとんど全部になる(多重極展開や局所展開のシフトも計算量のオーダー は同じだが、係数が2桁ほど小さい)。このため、他のところの計算量を増や してでもここを減らせれば大きな利得になる。

セル数を減らせばこの計算量は減る。そのかわり、最下層のセル に入っている粒子数が増えるので、直接計算のところの計算量が増えることに なる。この2つがバランスするようにセル数を決めると、セル当たりの粒子数 を に比例するようにとればいいことがわかる。このとき、実効的な計 算量のオーダーは になる[4]。

5.3 FFT による高速化

多重極展開から局所展開への変換やシフトは、展開係数のベクトルに変換行列 を掛ける操作になる。 Greengard と Rokhlin [9] はこの変換を FFT を使って高速化できることを示唆した。 Elliott と Board はこの方法を実現し、詳細な性能評価を行なった[6]。 例えば p=16までとったときには変換自体は3倍ほど高速化されている。ただ し、上に述べた直接計算とのトレードオフがあるので、計算全体の高速化は 倍程度ということになる。

5.4 並列化

並列化はツリー法、FMM の両方で良く研究されている。どちらでも、どのよう に空間分割をして粒子と領域をプロセッサに割り付けるかが問題となる。逆に いえば、それが決まれば並列化そのものはそれほど複雑ではない。メッセージ パッシングの機械では Warren と Salmon による ORB(再帰的直交分割)や Morton ordering による領域分割が良く知られている [17,18]。物理的に共有メモリである機械 や、分散共有メモリの場合は、Morton ordering によって粒子をソートしてお くことで自動的に空間分割が実現でき、かなり良い性能が得られている [11]。また、最近は HPF などのデータ並列型の言語を使っ た並列化も試みられている[12]。



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