Title: A New Version of the Fast Gauss Transform

The evaluation of the sum of $N$ Gaussians at $M$ points in space arises as a computational task in diffusion, fluid dynamics, finance, and, more generally, in mollification. The work required for direct evaluation grows like the product $NM$, rendering large-scale calculations impractical. We present an improved version of the fast Gauss transform [L. Greengard and J. Strain, {\em SIAM J. Sci. Stat. Comput.} {\bf 12}, 79 (1991)], which evaluates the sum of $N$ Gaussians at $M$ arbitrarily distributed points in $O(N+M)$ work, where the constant of proportionality depends only on the precision required. The new scheme is based on a diagonal form for translating Hermite expansions and is significantly faster than previous versions.

1991 Mathematics Subject Classification: 65R10 , 44A35, 35K05

Keywords and Phrases: diffusion, fast algorithms, Gauss transform

Full text: dvi.gz 18 k, dvi 41 k, ps.gz 71 k.

Home Page of DOCUMENTA MATHEMATICA