N体および粒子メッシュ法

多数の粒子間の相互重力または静電力の計算は、素朴な方法では粒子数の2乗に比例するコストがかかりますが、高速N体および粒子メッシュ法を用いることで、このコストをほぼ線形に削減でき、数百万粒子規模の銀河やプラズマのシミュレーションが可能になります。

Definition

N体および粒子メッシュ法は、多数の相互作用する粒子間の長距離力を、遠方の粒子をグループ化するか、またはグリッド上で場を解くことによって、2次未満の時間で近似するアルゴリズムです。

Scope

このトピックでは、長距離粒子相互作用のためのスケーラブルなアルゴリズムについて扱います。具体的には、Barnes-Hut法のような階層的ツリーコード、高速多重極展開法、およびグリッドベースの粒子メッシュ法と粒子-粒子粒子メッシュ法が含まれます。また、精度とコストのトレードオフ、およびこれらの手法が大規模な重力および静電シミュレーションにおいて果たす役割についても考察します。

Core questions

• なぜ、対となる長距離力を直接総和する方法は計算コストが法外に高くなるのでしょうか？
• ツリーコードは、遠方の粒子をどのようにグループ化して力計算のコストを削減するのでしょうか？
• 高速多重極展開法は、制御された誤差でどのようにほぼ線形のスケーリングを達成するのでしょうか？
• 粒子メッシュ法は、長距離力を扱うためにグリッド上で場をどのように解くのでしょうか？

Key theories

階層的ツリーコード

Barnes-Hutアルゴリズムは、遠方の粒子をセルにグループ化し、その集合的な力を重心によって近似することで、力評価のコストを2次からN log Nのオーダーに削減します。

高速多重極展開法

高速多重極展開法は、粒子のグループを切り捨てられた多重極展開によって表現し、それらを階層的に変換することで、厳密に制御可能な精度でほぼ線形のスケーリングを達成します。

粒子メッシュ法

粒子メッシュ法および粒子-粒子粒子メッシュ法は、電荷または質量をグリッドに補間し、高速フーリエ変換を用いて場を解き、短距離補正を加えることで、長距離相互作用を効率的に処理します。

Clinical relevance

これらの手法は、構造形成の宇宙論的および銀河N体シミュレーション、プラズマシミュレーション、および大規模分子系の長距離静電相互作用を推進しており、高速多重極展開法は20世紀の最も重要なアルゴリズムの一つとして認識されています。

History

粒子メッシュ法は1980年代にHockneyとEastwoodによって体系化されました。1986年のBarnes-Hutツリーコードと1987年のGreengardとRokhlinによる高速多重極展開法は、N体シミュレーションを変革し、その後の大規模な宇宙論的および分子シミュレーションを可能にしました。

Key figures

• Josh Barnes
• Piet Hut
• Leslie Greengard
• Vladimir Rokhlin

Seminal works

• barneshut1986
• greengard1987

Frequently asked questions

なぜすべての対となる力を直接計算しないのですか？

直接総和のコストは粒子数の2乗に比例して増加するため、粒子数を2倍にすると計算量が4倍になり、宇宙論的シミュレーションや大規模分子シミュレーションにおける数百万または数十億の粒子に対しては不可能になります。高速な手法はこれをほぼ線形のコストに削減します。

ツリー法と多重極展開法はどのように誤差を制御するのですか？

これらの方法は、遠方の粒子群の影響を近似し、より多くの多重極項を含めるか、より厳密な開口基準を使用することで近似を洗練させます。これにより、精度と速度のトレードオフを制御された方法で行うことができます。