The Fast Gauss Transform

Abstract

Many problems in applied mathematics require the evaluation of the sum of N Gaussians at M points in space. The work required for direct evaluation grows like $NM$ as N and M increase; this makes it very expensive to carry out such calculations on a large scale. In this paper, an algorithm is presented which evaluates the sum of N Gaussians at M arbitrarily distributed points in $C \cdot (N + M)$ work, where C depends only on the precision required. When $N = M = 100,000$, the algorithm presented here is several thousand times faster than direct evaluation. It is based on a divide-and-conquer strategy, combined with the manipulation of Hermite expansions and Taylor series.