计算数学中的快速多极算法 快速多极算法是一种用于加速粒子间相互作用计算的数值方法，特别适用于N体问题。当需要计算大量粒子之间的相互作用时，直接计算所有粒子对之间的力（其计算复杂度为O(N²)）在N很大时（例如数百万或数十亿）会变得极其昂贵，甚至不可行。快速多极算法通过一种层次化的近似，将计算复杂度降低到O(N)或O(N log N)，使得大规模模拟成为可能。 第一步：理解问题的核心——N体问题与直接求和的局限性 考虑一个经典问题：计算N个粒子在空间中的引力（或静电力）相互作用。每个粒子i受到其他所有粒子j的力的作用，这个力通常与距离的平方成反比（例如，万有引力定律，库仑定律）。我们需要计算每个粒子i上的合力。 直接的方法是进行双重循环，对每一对粒子(i, j)计算相互作用力。这需要大约N(N-1)/2次计算，计算复杂度为O(N²)。当N=1,000,000时，这大约是5×10¹¹次计算，对于普通计算机来说已经非常耗时。 第二步：基本思想——用“远近似”代替“直接求和” 快速多极算法的核心思想非常直观：对于任何一个粒子，离它很近的粒子对它的作用力需要精确计算；而离它很远的、大群的粒子对它的作用力，则可以近似地用一个或少数几个等效的“源”来表示。 这类似于在地球上感受太阳的引力。我们并不需要计算太阳内部每一个氢原子对我们的引力，而是可以将太阳的全部质量看作集中在质心上的一个点质量，这个点质量产生的引力场就足够精确了。这就是“多极展开”的物理图像：将一片分布复杂的粒子群所产生的场，用位于某个中心点的“多极子”（单极子-总电荷/质量、偶极子、四极子等）的场来近似。 第三步：实现远近分离的关键技术——分层与树结构 如何高效地判断哪些粒子“远”，哪些粒子“近”？如何组织这些“远”的粒子群？快速多极算法通过以下步骤实现： 构建层次结构（树） ：将包含所有粒子的整个空间定义为根节点。然后将这个空间不断进行八等分（在三维中）或四等分（在二维中），形成一棵树（称为八叉树或四叉树）。每个小立方体（或正方形）是树的一个节点。这个过程递归进行，直到每个叶子节点只包含少量粒子（比如几十个）。 定义“近邻”与“远邻” ：对于一个给定的目标节点（一个小立方体），其“近邻”定义为与其直接相邻的节点（包括自身）。所有其他节点都是“远邻”。有一个重要的判断准则：一个远邻节点的任何粒子，到目标节点中任何粒子的距离，都相对于该节点的大小是“远”的。 上行过程（P2M, M2M） ：从树的叶子节点开始，向上传递信息。 粒子到多极子（P2M） ：计算每个叶子节点内所有粒子的合并效应，用一组多极展开系数表示，这个展开的中心是该节点的中心。 多极子到多极子（M2M） ：当一个父节点需要计算其多极展开时，它不需要重新遍历其内部所有粒子。相反，它可以将其子节点的多极展开（以子节点中心为原点）进行平移，合并成以父节点中心为原点的新的多极展开系数。这个过程从叶子节点向上进行，直到根节点。 第四步：力的计算——下行过程与直接求和 交互列表 ：对于树中的每一个节点，我们定义一个“交互列表”。这个列表包含该节点的父节点的“近邻”节点的子节点中，又不是该节点自身的“近邻”的那些节点。简单说，就是那些足够“远”（可以应用近似），但又足够“近”（其多极展开在当前节点处仍然有效）的节点集合。 多极子到局部展开（M2L） ：对于目标节点，遍历其交互列表。将列表中每个节点的多极展开（描述了一群远粒子的影响）进行转换，转换成在目标节点中心处的“局部展开”。局部展开描述了远处粒子群在目标节点附近产生的场的近似形式。 下行过程（L2L, L2P） ： 局部展开到局部展开（L2L） ：将父节点的局部展开（描述了所有远邻的影响）平移并传递给它的子节点。 局部展开到粒子（L2P） ：当到达叶子节点时，将存储在该节点的局部展开系数在每个粒子的位置进行求值，从而得到所有“远邻”粒子对该粒子的合力的近似值。 近邻直接计算（P2P） ：最后，对于每个粒子，其“近邻”节点内的所有粒子对其产生的力，仍然采用直接求和的方法精确计算。因为近邻粒子数量有限，这部分计算复杂度是O(N)。 第五步：总结与算法优势 通过上述过程，快速多极算法将力的计算分为两部分： 远场作用 ：通过多极展开和局部展开进行近似，计算复杂度为O(N)。 近场作用 ：通过直接计算，由于树结构保证了近邻粒子数有限，计算复杂度也是O(N)。 因此，整个算法的总计算复杂度从直接法的O(N²)降低到了O(N)或O(N log N)，使得模拟数百万甚至数十亿粒子的系统成为可能。该算法在计算天体物理、分子动力学、流体力学（边界元法）等领域有极其重要的应用。