N-body gravity simulation in O(N)

**TL;DR:** 视频详细讲解了如何用快速多极子方法（FMM）在 O(N) 时间内实现 N 体引力模拟，并对比了朴素 O(N²) 和 Barnes-Hut O(N log N) 的局限，重点介绍了复数、多极展开和局部展开的数学原理。 ## 概述 这段视频展示了一个实时运行的 N 体模拟，数十万个粒子相互施加引力。常见的实现有两种：朴素暴力法（O(N²)）和 Barnes-Hut 算法（O(N log N)）。视频作者原本打算实现 Barnes-Hut，但调研后发现它“不够酷，而且误差难界”。一个偶然的链接引出了 **快速多极子方法（Fast Multipole Method, FMM）**： - 由 Leslie Greengard 和 Vladimir Rokhlin 于 1987 年提出 - 时间复杂度 O(N) - 误差有严格的数学界 - 被评为 20 世纪十大算法之一 ## 从朴素暴力到分层思想 N 体问题是计算 N 个粒子之间的引力。在二维空间中，引力大小与质量乘积成正比，除以距离（不平方），力向量由势函数的梯度得到。 ### 复数简化势函数 二维势函数与距离的对数有关。将粒子位置视为复数，位移写成极坐标形式，对数内部的乘积可以拆分为和。复数的实部恰好是模的对数。 借助**柯西-黎曼方程**，复可微函数的导数可以用偏导数表示。力等于势函数梯度的相反数，通过复导数可以简洁地得到力的复数表达式。 ### 分层方法 FMM 和 Barnes-Hut 都使用四叉树（二维）将粒子分层组织。树节点包含一个盒子，每个层级可细分为四个子盒。这样可以将粒子分为近场（需精确计算）和远场（可近似）。 Barnes-Hut 用质心近似一个远场簇，判据是节点大小与粒子距离的比值小于阈值 θ。但它仍然是逐个粒子计算远场，且质心近似精度有限。 ## 快速多极子方法的核心：多极展开 为了更精确地近似一个簇的远场势，FMM 使用**多极展开**： - 将源簇的势函数写成关于原点（通常是节点中心）的洛朗级数形式。 - 系数 \(A_k\) 只依赖于源的位置和质量，可以预先计算。 - 求值时只需代入目标位置 \(Z\) 的负幂次。 这个级数在簇的收敛半径（即簇的包围圆）外收敛。误差上界为： \[ \left| \Phi(Z) - \Phi_P(Z) \right| \le \frac{\sum m_i}{R} \cdot \frac{(R/|Z|)^{P+1}}{1 - R/|Z|} \] 误差随 \(R/|Z|\) 指数衰减。取 \(P=10\) 时误差已几乎不可见。 与 Barnes-Hut 不同，FMM 的多极展开以节点中心（而非质心）为原点，以保证收敛半径可控。 ## 局部展开：真正的加速 多极展开只能从远场源广播到单个目标点。要彻底避免逐个粒子计算，FMM 引入了**局部展开**：以目标盒子为中心，收集所有远处源的多极展开，合并成一个关于目标中心点的级数。这样，对目标盒子内的所有粒子只需一次求值。 局部展开同样写成洛朗级数形式，其系数由远处源的多极系数通过“平移”得到。整个过程分为三步： 1. **向上树**：计算每个节点的多极展开（从叶子到根）。 2. **向下树**：将父节点的局部展开向下传递，并与兄弟节点的多极展开转换得到的局部展开合并。 3. **直接计算**：对近场粒子（同一节点或相邻节点）采用朴素暴力。 由于每个节点的多极展开和局部展开只需 O(P²) 或 O(P log P) 操作，而树深度为 O(log N)，整体复杂度为 O(N)。 ## 误差分析 FMM 的误差来源于多极展开和局部展开的截断。可以通过选择合适的截断阶数 \(P\) 来控制精度。视频中给出了指数级的误差上界，实际应用中 \(P\) 通常取 10~20 即可达到令人满意的精度。 ## 总结 快速多极子方法通过**多极展开**和**局部展开**，将 O(N²) 的暴力计算降为 O(N)，同时保证了误差可界。它比 Barnes-Hut 更快、更精确，是实现大规模 N 体模拟的黄金标准。视频最后展示了实时运行的效果，数十万个粒子流畅互动，验证了算法的有效性。 **Source:** [https://www.youtube.com/watch?v=FhMftauQZqU](https://www.youtube.com/watch?v=FhMftauQZqU)