高速多重極法

高速多重極法（FMM ）は、n体問題における長距離力の計算を高速化するために開発された数値手法である。これは、多重極展開を使用してシステムグリーン関数を展開することで実現され、これにより、互いに近接するソースをグループ化し、それらを単一のソースであるかのように扱うことができる。^[1]

FMM は、計算電磁気学の問題^[2]、特に計算生体電磁気学に適用されるモーメント法(MOM)の反復ソルバーの高速化にも適用されています。 FMM は、 Leslie GreengardとVladimir Rokhlin Jr. ^[3]によって最初にこの方式で導入され、ベクトルヘルムホルツ方程式の多重極展開に基づいています。 FMM を使用して遠く離れた基底関数間の相互作用を処理することにより、対応する行列要素を明示的に格納する必要がなくなり、必要なメモリが大幅に削減されます。 次に FMM を階層的に適用すると、反復ソルバーの行列ベクトル積の複雑度を有限演算で から に改善できます。つまり、許容値が である場合、行列ベクトル積は許容値内に収まることが保証されます。複雑度の許容値への依存性はであり、つまり FMM の複雑度は です。これにより、MOM の適用範囲が、これまで可能だったよりもはるかに大きな問題にまで拡大されました。 ${\displaystyle {\mathcal {O}}(N^{2})}$${\displaystyle {\mathcal {O}}(N)}$${\displaystyle \epsilon }$${\displaystyle \epsilon .}$${\displaystyle \epsilon }$${\displaystyle {\mathcal {O}}(\log(1/\varepsilon ))}$${\displaystyle {\mathcal {O}}(N\log(1/\varepsilon ))}$

Rokhlin Jr.とGreengardによって導入されたFMMは、20世紀のトップ10アルゴリズムの1つと言われています。 ^[4] FMMアルゴリズムは、多くの物理システムから発生する可能性のある特定の種類の密行列を含む行列ベクトル乗算の複雑さを軽減します。

FMM は、ハートリー・フォック法や量子化学における密度汎関数理論計算におけるクーロン相互作用の効率的な処理にも応用されています。

最も単純な形式では、高速多重極法は次の関数を評価します。

${\displaystyle f(y)=\sum _{\alpha =1}^{N}{\frac {\phi _{\alpha }}{y-x_{\alpha }}}}$、

ここで、は極の集合であり、はの点の集合上の対応する極の重みです。 これは問題の 1 次元形式ですが、アルゴリズムは 以外の多次元およびカーネルに簡単に一般化できます。 ${\displaystyle x_{\alpha }\in [-1,1]}$${\displaystyle \phi _{\alpha }\in \mathbb {C} }$${\displaystyle \{y_{1},\ldots ,y_{M}\}}$${\displaystyle y_{\beta }\in [-1,1]}$${\displaystyle (yx)^{-1}}$

単純に言えば、点を評価するには演算が必要です。高速多重極法の背後にある重要な観察は、との間の距離が十分に大きい場合、 は多項式によって十分に近似されるということです。具体的には、を次数 のチェビシェフノードとし、 を対応するラグランジュ基底多項式とします。補間多項式は次のようになります。 ${\displaystyle f(y)}$${\displaystyle M}$${\displaystyle {\mathcal {O}}(ミネソタ州)}$${\displaystyle y}$${\displaystyle x}$${\displaystyle (yx)^{-1}}$${\displaystyle -1<t_{1}$${\displaystyle p\geq 2}$${\displaystyle u_{1}(y),\ldots ,u_{p}(y)}$

${\displaystyle {\frac {1}{yx}}=\sum _{i=1}^{p}{\frac {1}{t_{i}-x}}u_{i}(y)+\epsilon _{p}(y)}$

極が補間領域から十分離れている場合、およびであれば、多項式次数 で急速に収束します。これは「局所展開」として知られています。 ${\displaystyle |\epsilon _{p(y)}|<5^{-p}}$${\displaystyle |x|\geq 3}$${\displaystyle |y|<1}$

高速多重極法の高速化は、この補間から生まれます。すべての極が「遠く離れている」場合、 のコストでチェビシェフノードのみの合計を評価し、 のコストでそれをすべての目的のポイントに補間します。 ${\displaystyle {\mathcal {O}}(Np)}$${\displaystyle {\mathcal {O}}(Mp)}$

${\displaystyle \sum _{\alpha =1}^{N}{\frac {\phi _{\alpha }}{y_{\beta }-x_{\alpha }}}=\sum _{i=1 }^{p}u_{i}(y_{\beta })\sum _{\alpha =1}^{N}{\frac {1}{t_{i}-x_{\alpha }}}\ファイ_{\アルファ }}$

（数値許容差）なので、総コストは です。 ${\displaystyle p=-\log _{5}\epsilon }$${\displaystyle \epsilon }$${\displaystyle {\mathcal {O}}((M+N)\log(1/\epsilon ))}$

極が確実に十分に分離されていることを確認するには、単位区間を再帰的に細分化して、各区間に極のみが配置されるようにします。次に、各区間内で明示的な式を使用し、十分に分離されているすべての区間に対して補間を行います。これにより、指定された許容範囲内のレベル しか必要としないため、スケーリングが損なわれることはありません。${\displaystyle {\mathcal {O}}(p)}$${\displaystyle \log(1/\epsilon )}$

• バーンズ・ハットシミュレーション
• 多極展開
• n体シミュレーション

• ギブソン、ウォルトン C. 『電磁気学におけるモーメント法（第 3 版）』、Chapman & Hall/CRC、2021 年。ISBN 9780367365066。 
• グリーンガードとロクリンによる原著論文の要約
• Rick Beatson と Leslie Greengard による高速多重極法の短期コース。
• 高速多重極法の JAVA アニメーション さまざまな適応を備えた高速多重極法の素晴らしいアニメーション。

• Puma-EM 高性能で並列化されたオープンソースのモーメント法/マルチレベル高速多重極法の電磁気学コード。
• KIFMM3d カーネル非依存高速多重極 3D 法 (kifmm3d) は、基礎となるカーネルの明示的な多重極展開を必要とせず、カーネル評価に基づいた新しい FMM 実装です。
• PVFMM 粒子およびボリューム ソースからのポテンシャルを計算するための KIFMM の最適化された並列実装。
• FastBEM 2D/3D ポテンシャル、弾性、ストークス流、音響の問題を解決するための無料の高速多重極境界要素プログラム。
• FastFieldSolvers は、FMM を使用して Maxwell 方程式を解き、回路寄生 (インダクタンスと静電容量) を抽出するために MIT で開発された FastHenry および FastCap と呼ばれるツールの配布を管理します。
• ExaFMM ExaFMM は、並列スケーラビリティに重点を置いた、ラプラス/ヘルムホルツ カーネル用の CPU/GPU 対応 3D FMM コードです。
• ScalFMM は、汎用性と並列化（ OpenMP / MPIを使用）を重視してInria Bordeauxで開発された C++ ソフトウェア ライブラリです。2017 年 5 月 2 日にWayback Machineにアーカイブされました。
• DASHMM DASHMM は、インディアナ大学で非同期マルチタスク HPX-5 ランタイム システムを使用して開発された C++ ソフトウェア ライブラリです。共有および分散メモリ コンピューター上での統一された実行を提供し、3D ラプラス、湯川、およびヘルムホルツ カーネルを提供します。
• マルチコア上で動的並列処理を実現する RECFMM 適応型 FMM。