The Fast Gauss Transform with Variable Scales

This paper presents a fast algorithm that evaluates a d-dimensional Gaussian convolution sum with scales that vary from point to point. This algorithm evaluates the sum of N Gaussians at M arbitrarily distributed points in $C(N + M)$ work, where C depends only on the precision required and the essential minimum of the scales. It achieves a speedup of almost 2,000 with $N = M = 100,000$, $d = 2$, and scales bounded below by $1/100$.