algorithm - 高速多重極法の実装に関する推奨事項？

Question

反発粒子のシステムを効率的にシミュレートするために、高速多重極法を実装することに興味があります。

FMMについて議論している参考文献の大規模なコレクションを見つけましたが、アルゴリズムを完全に理解したい非数学者にとって非常に親しみやすいものはないようです。

プロセスの背後にある数学を明確に説明し、適切な実装を例示する擬似コードを含む、基礎的なリファレンスをお勧めできますか？

Answer 1

FMMのショート コースが好きです。では、複素変数の理論を使用して 2D で FMM を実行するよりも、1D で FMM から始まります。さらに、球面調和関数の理論を使用するクレイジーな 3D バージョンもありますが、数学者ではない人にとっては非常に難しいと思います。しかし、2D でのみ FMM が必要な場合は問題ありません。

残念ながら、そこには疑似コードはありません。

しかし、FMM の精度は本当に必要なのでしょうか? Barnes-Hut のアルゴリズムで問題ないかもしれません

Answer 2

私は決して FMM の専門家ではありませんが、このJava の実装と紹介は、これまでに見つけた中で、注意深くゆっくりと説明するための最良の情報源です。この論文は、用語を使用する前に用語を定義するのに優れており、コードは少なくとも参照ポイントとして役立ちます。数学はまだ非常にすぐに毛むくじゃらになりますが、それはそれです:)

高速多極子法への歩行者向けの紹介は、僅差の 2 番目です。実際に動作する FMM 実装の詳細については説明していませんが、基本的な考え方を紹介するのに適しています。