Effective convolution method such as sum estimation

Question

Problem . For N three-dimensional points, which are {$ p_1, p_2, .., p_n $}, where $ p_i = (x_i, y_i, z_i) $. I have to find the value of the formula

for some given constant integers P, Q, R, S. all numbers are between 1 and M (= 100).

I need an efficient method to calculate this formula

Please give an idea of ​​how to reduce complexity better than $ O (n ^ 2) $

Answer 1

Assuming all coordinates are between 1 and 100, you can do this in:

• O (100 * 100 * 100).

• FFT

3D- . .

, . .

Answer 2

(, ), "" (x_j, y_j), i-th.

, , - Fast Multipole. , , . .