N体和粒子网格方法

天真地计算许多粒子之间的相互引力或静电力，其成本是粒子数量的平方，而快速N体和粒子网格方法将其降低到接近线性，从而使星系和等离子体的百万粒子模拟成为可能。

Definition

N体和粒子网格方法是通过将远距离粒子分组或在网格上求解场，以低于二次方的时间近似计算许多相互作用粒子之间远程力的算法。

Scope

本主题涵盖用于远程粒子相互作用的可扩展算法：分层树代码（如Barnes-Hut）、快速多极子方法以及基于网格的粒子网格和粒子-粒子粒子网格方案。它讨论了精度与成本的权衡，以及这些方法在大型引力场和静电场模拟中的作用。

Core questions

• 为什么直接求和成对远程力会非常昂贵？
• 树代码如何将远距离粒子分组以降低力计算成本？
• 快速多极子方法如何实现受控误差下的近线性缩放？
• 粒子网格方法如何通过在网格上求解场来处理远程力？

Key theories

分层树代码

Barnes-Hut算法将远距离粒子分组到单元中，其集体力通过它们的质心近似，将力评估的成本从二次方降低到N log N阶。

快速多极子方法

快速多极子方法通过截断多极子展开式表示粒子群，并对其进行分层平移，从而在严格可控的精度下实现近线性缩放。

粒子网格方法

粒子网格和粒子-粒子粒子网格方案将电荷或质量插值到网格上，通过快速傅里叶变换求解场，并添加短程校正，从而有效地处理远程相互作用。

Clinical relevance

这些方法推动了宇宙学和星系N体结构形成模拟、等离子体模拟以及大型分子系统的远程静电模拟，而快速多极子方法被认为是二十世纪最重要的算法之一。

History

粒子网格方法在20世纪80年代由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

为什么不直接计算每个成对力？

直接求和的成本随粒子数量的平方增长，因此粒子数量翻倍会使工作量增加四倍，这对于宇宙学和大型分子模拟中数百万或数十亿的粒子来说是不可能的。快速方法将其成本降低到接近线性。

树方法和多极子方法如何控制其误差？

它们近似计算远距离粒子群的影响，并通过包含更多多极子项或使用更严格的开放准则来细化近似，从而可以在受控的方式下权衡精度和速度。