Fast convolution with free-space Green's functions
This provides a simple, fast, and accurate method for computing volume potentials, which is useful for researchers working on integral equations and preconditioners in computational science.
The paper introduces a fast algorithm for computing volume potentials (convolution of free-space Green's functions with source distributions on uniform grids) that achieves superalgebraic convergence for smooth data using FFT and regularization. The method also enables rapid computation of any derivative of the potential with an extra FFT.
We introduce a fast algorithm for computing volume potentials - that is, the convolution of a translation invariant, free-space Green's function with a compactly supported source distribution defined on a uniform grid. The algorithm relies on regularizing the Fourier transform of the Green's function by cutting off the interaction in physical space beyond the domain of interest. This permits the straightforward application of trapezoidal quadrature and the standard FFT, with superalgebraic convergence for smooth data. Moreover, the method can be interpreted as employing a Nystrom discretization of the corresponding integral operator, with matrix entries which can be obtained explicitly and rapidly. This is of use in the design of preconditioners or fast direct solvers for a variety of volume integral equations. The method proposed permits the computation of any derivative of the potential, at the cost of an additional FFT.