卷积的有效方法，如求和评估
Efficient method for convolution like sum evaluation
问题 给定 N 个 3 维点，它们是 {$p_1,p_2,..,p_n$} 其中 $ p_i = (x_i,y_i,z_i) $ .我必须找到公式的值
对于一些给定的常数整数 P、Q、R、S。
所有数字都在 1 和 M ( = 100) 之间。
我需要一个有效的方法来计算这个公式
请给出关于如何比 $O(n^2)$
更好地降低复杂性的想法
假设所有坐标都在 1 到 100 之间，那么您可以通过：
计算所有点的 3d 直方图 O(100*100*100) 操作。
使用 FFT 计算直方图沿 3 个轴中每个轴的卷积
这将产生 3d 向量的 3d 直方图。然后您可以遍历此直方图以计算所需的值。
要点是，计算值直方图的卷积就是计算这些值的两两差值的直方图。这也可以用于以类似的方式计算值总和的直方图。
你的问题看起来像一个粒子势问题（例如你在电动力学中遇到的那种），你必须在位置 (x_j, y_j) 找到一些 "potential" i-th 个粒子。
针对此 class 问题的快速算法是快速多极方法。查找此关键字，但我必须警告您，它绝不是易于理解或实现的。需要强大的数学背景。
问题 给定 N 个 3 维点，它们是 {$p_1,p_2,..,p_n$} 其中 $ p_i = (x_i,y_i,z_i) $ .我必须找到公式的值
对于一些给定的常数整数 P、Q、R、S。 所有数字都在 1 和 M ( = 100) 之间。
我需要一个有效的方法来计算这个公式
请给出关于如何比 $O(n^2)$
更好地降低复杂性的想法假设所有坐标都在 1 到 100 之间，那么您可以通过：
计算所有点的 3d 直方图 O(100*100*100) 操作。
使用 FFT 计算直方图沿 3 个轴中每个轴的卷积
这将产生 3d 向量的 3d 直方图。然后您可以遍历此直方图以计算所需的值。
要点是，计算值直方图的卷积就是计算这些值的两两差值的直方图。这也可以用于以类似的方式计算值总和的直方图。
你的问题看起来像一个粒子势问题（例如你在电动力学中遇到的那种），你必须在位置 (x_j, y_j) 找到一些 "potential" i-th 个粒子。
针对此 class 问题的快速算法是快速多极方法。查找此关键字，但我必须警告您，它绝不是易于理解或实现的。需要强大的数学背景。