Improved Fast Gauss Transform

Abstract

The fast Gauss transform proposed by Greengard and Strain reduces the computational complexity of the evaluation of the sum of $N$ Gaussians at $M$ points in $d$ dimensions from $O(MN)$ to $O(M+N)$. However, the constant factor in $O(M+N)$ grows exponentially with increasing dimensionality $d$, which makes the algorithm impractical in higher dimensions. In this paper we present an improved fast Gauss transform where the constant factor is reduced to asymptotically polynomial order. The reduction is based on a new multivariate Taylor expansion scheme combined with the space subdivision using the $k$-center algorithm. The complexity analysis and error bound are presented which helps to determine parameters automatically given a desired precision to which the sum must be evaluated. We present numerical results on the performance of our algorithm and provide numerical verification of the corresponding error estimate. (UMIACS-TR-2003-64)