高速多重極法

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

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

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

FMMは、ハートリー・フォック法や量子化学における密度汎関数理論計算におけるクーロン相互作用を効率的に扱うためにも応用されている。^{[ 5 ] [ 6 ]}

アルゴリズムのスケッチ

高速多重極法 – 5次チェビシェフ多項式によるx = 3の極の補間

高速多重極法は、最も単純な形では、次の関数を評価します。 ここで、は極の集合であり、は を満たす点の集合における対応する極の重みです。これは問題の1次元形式ですが、このアルゴリズムは 以外の多次元およびカーネルにも簡単に一般化できます。 $${\displaystyle f(y)=\sum _{\alpha =1}^{N}{\frac {\phi _{\alpha }}{y-x_{\alpha }}},}$$ ${\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 (y-x)^{-1}}$ ${\displaystyle -1<t_{1}<\ldots <t_{p}<1}$ ${\displaystyle p\geq 2,}$ ${\displaystyle u_{1}(y),\ldots ,u_{p}(y)}$ $${\displaystyle {\frac {1}{y-x}}=\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 }}}\phi _{\alpha }.}$$

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

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

参照

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

参考文献

1. Rokhlin, Vladimir (1985). 「古典ポテンシャル理論の積分方程式の高速解法」J. Computational Physics Vol. 60, pp. 187–207.
2. Nader Engheta、William D. Murphy、 Vladimir Rokhlin、およびMarius Vassiliou（1992）、「電磁散乱計算のための高速多重極法」、IEEE Transactions on Antennas and Propagation 40、634–641。
3. 「高速多重極法」 。 2011年6月3日時点のオリジナルよりアーカイブ。2010年12月10日閲覧。
4. Cipra, Barry Arthur (2000年5月16日). 「20世紀のベスト：編集者が選ぶトップ10アルゴリズム」 . SIAM News . 33 (4). Society for Industrial and Applied Mathematics : 2. 2018年9月20日時点のオリジナルよりアーカイブ。 2019年2月27日閲覧。
5. White, Christopher A.; Johnson, Benny G.; Gill, Peter MW; Head-Gordon, Martin (1994年11月). 「連続高速多重極法」. Chemical Physics Letters . 230 ( 1–2 ): 8–16 . doi : 10.1016/0009-2614(94)01128-1 .
6. White, Christopher A.; Johnson, Benny G.; Gill, Peter MW; Head-Gordon, Martin (1996年5月). 「連続高速多重極法による線形スケーリング密度汎関数計算」. Chemical Physics Letters . 253 ( 3–4 ): 268– 278. doi : 10.1016/0009-2614(96)00175-3 .

さらに読む

• Yijun Liu:高速多重極境界要素法: 理論と工学への応用、ケンブリッジ大学出版局、ISBN 978-0-521-11659-6 (2009)。

外部リンク

• ギブソン、ウォルトン C. 『電磁気学におけるモーメント法（第 3 版）』、チャップマン & ホール/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++ソ​​フトウェアライブラリです。共有メモリ型および分散メモリ型のコンピュータ上で統合実行を提供し、3次元ラプラスカーネル、湯川カーネル、ヘルムホルツカーネルを提供します。
• マルチコア上で動的並列処理を実現するRECFMM適応型 FMM。
• FMM3Dマルチコア マシン上で効率的な 3D N 体相互作用計算を行うライブラリ。