Multidimensional Fast Gauss Transforms by Chebyshev Expansions

A new version of the fast Gauss transform (FGT) is introduced which is based on a truncated Chebyshev series expansion of the Gaussian. Unlike the traditional fast algorithms, the scheme does not subdivide sources and evaluation points into multiple clusters. Instead, the whole problem geometry is treated as a single cluster. Estimates for the error as a function of the dimension d and the expansion order p will be derived. The new algorithm has order ${d+p+1\choose d}(N+M)$ complexity, where M and N are the number of sources and evaluation points. For a fixed p, this estimate is only polynomial in d. However, to maintain accuracy it is necessary to increase p with d. The precise relationship between d and p is investigated analytically and numerically.