Fast convolution with free-space Green's functions

© 2016. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/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. (C) 2016 Elsevier Inc. All rights reserved.This work was supported in part by the Applied Mathematical Sciences Program of the U.S. Department of Energy under Contract DEFGO288ER25053 and by the Office of the Assistant Secretary of Defense for Research and Engineering and AFOSR under NSSEFF Program Award FA9550-10-1-0180. The authors would like to thank Lise-Marie Imbert-Gerard and Carlos Borges for several useful conversations. The authors would also like to thank the ASIC (Area de Sistemas de Informacion y Comunicaciones) and Francisco Jose Rosich Viana for technical support and access to the UPV super-computing cluster RIGEL.Vico Bondía, F.; Greengard, L.; Ferrando Bataller, M. (2016). Fast convolution with free-space Green's functions. Journal of Computational Physics. 323:191-203. doi:10.1016/j.jcp.2016.07.028S19120332