咱们先把问题背景理清楚：假设我们有一个有限体积的区域$V$，还有一个有界光滑函数$g: \mathbb R^3\to\mathbb R$，以及一个核函数$K$，我们定义函数$f: \mathbb R^3\to\mathbb R$为：
$$
f(\mathbf x) = \int_V K(\mathbf x, \mathbf x')g(\mathbf x');d^3\mathbf x'
$$

现在我们已经在一个包含$N$个点的结构化网格上得到了$g$的离散形式，想要在同一个网格上求出$f$的离散版本。这个核函数的形式是：
$$
K(\mathbf x, \mathbf x') = \frac{1}{|\mathbf x - \mathbf x'|^p}
$$
其中$p\ge 1$是自然数。

最直接的思路就是用常规数值积分来计算，但这么做的复杂度是$O(N^2)$——毕竟每个网格点都要遍历所有$N$个源点来累加贡献，当$N$很大的时候速度会慢到没法用。那有没有办法把复杂度降到$O(N)$呢？这里给你几个可行的方案：

• 快速多极子方法（Fast Multipole Method, FMM）：这是处理这类径向核积分的经典线性复杂度算法。它的核心逻辑是把空间划分成不同层级的嵌套盒子，对于每个目标点：

  • 近处的源点（同一个小盒子或者相邻盒子里的点）直接计算精确贡献；
  • 远处的源点则通过“多极展开”把整个远盒子的源近似成一个等效的聚合源，只需要计算这个聚合源对目标点的贡献，不用逐个遍历远盒子里的所有点。
    对于$1/|\mathbf x - \mathbf x'|^p$这种径向核，FMM有非常成熟的实现，而且完全适配结构化网格的场景，能稳定做到$O(N)$的计算复杂度。

• 简化版分层网格近似（适合对精度要求稍低的场景）：如果你的$p$取值较小（比如$p=1$或$2$），而且网格是规则结构化的，可以把空间分成大小递增的块。对于每个目标点，远处的块用块内$g$的加权平均值来近似整个块的贡献，不用逐个计算块内的每个点。这种方法本质是FMM的简化实现，同样能达到$O(N)$的复杂度，实现起来会更简单，但精度需要根据你的需求调整参数。

• 必须注意的奇点处理：当$\mathbf x$和$\mathbf x'$重合时，核函数会出现奇点（分母为0）。在离散计算时，一定要单独处理每个点自身的贡献——比如在该点周围的小网格单元内做解析积分，或者用极高精度的局部数值积分来近似，避免直接代入离散点导致的数值发散或错误。

备注：内容来源于stack exchange，提问作者kid