数值椭圆型方程的快速多极算法 快速多极算法（FMM）是一种用于高效计算N体问题的数值方法，特别适用于求解椭圆型偏微分方程。我将从基础概念开始，逐步讲解其原理和应用。 首先，椭圆型方程描述了稳态物理现象，如静电势、引力势或稳态热传导。这类方程的解可以表示为积分形式，例如泊松方程的解可通过格林函数表示为源项积分。当使用边界元法或粒子方法离散时，需计算所有离散点间的相互作用，直接计算复杂度为O(N²)，计算量随问题规模急剧增加。 为解决此问题，FMM利用势场在远距离的平滑性，通过多极展开和局部展开近似远场相互作用。其核心思想是将计算区域分层细分（如使用八叉树结构），在近场区域直接计算相互作用，在远场区域通过聚合-转移-配置步骤近似计算。具体步骤包括：1. 多极展开：将源点群的贡献聚合为多极矩；2. 多极到多极转换：在树结构上层传递聚合信息；3. 多极到局部转换：将远场多极矩转换为局部展开系数；4. 局部到局部转换：在树结构下层传递局部信息；5. 局部展开求值：计算远场对目标点的贡献。 FMM的关键在于展开截断误差控制，通常使用球谐函数或泰勒展开，截断阶数p决定计算精度。通过合理选择p，FMM可将复杂度降至O(N)或O(N log N)，同时保持可控误差。此方法已广泛应用于计算电磁学、流体力学和分子动力学等领域，大幅提升了大规模椭圆型方程的计算效率。