Fast convolution with the free space Helmholtz Green's function

We construct an approximation of the free space Green's function for the Helmholtz equation that splits the application of this operator between the spatial and the Fourier domains, as in Ewald's method for evaluating lattice sums. in the spatial domain we convolve with a sum of decaying Gaussians; with positive coefficients and, in the Fourier domain, we multiply by a band-limited kernel. As a part of our approach, we develop new quadratures appropriate for the singularity of Green's function in the Fourier domain. The approximation and quadratures yield a fast algorithm for computing volumetric convolutions with Green's function in dimensions two and three. The algorithmic complexity scales as O(K(d) log K + C(log epsilon(-1))(d)), where epsilon is selected accuracy, kappa is the number of wavelengths in the problem, d is the dimension, and C is a constant. The algorithm maintains its efficiency when applied to functions with singulafities. In contrast to the Fast Multipole Method, as K -> 0, our approximation makes a transition to that of the free space Green's function for the Poisson equation. We illustrate our approach with examples. (C) 2008 Elsevier Inc. All rights reserved.