The anisotropic truncated kernel method for convolution with free-space Green's functions

A common task in computational physics is the convolution of a translation invariant, free-space Green's function with a smooth and compactly supported source density. Fourier methods are natural in this context but encounter two difficulties. First, the kernel is typically singular in Fourier space, and second, the source distribution can be highly anisotropic. The truncated kernel method [F. Vico, L. Greengard, and M. Ferrando, J. Comput. Phys., 323(2016), pp. 191-203] overcomes the first difficulty by taking into account the spatial range over which the solution is desired and setting the Green's function to zero beyond that range in a radially symmetric fashion. The transform of this truncated kernel can be computed easily and is infinitely differentiable by the Paley-Wiener theorem. As a result, a simple trapezoidal rule can be used for quadrature, the convolution can be implemented using the fast Fourier transform, and the result is spectrally accurate. Here, we develop an anisotropic extension of the truncated kernel method, where the truncation region in physical space is a rectangular box, which may have a large aspect ratio. In this case, the Fourier transform of the truncated kernel is again smooth, but is typically not available analytically. Instead, an efficient sum-of-Gaussians approximation is used to obtain the Fourier transform of the truncated kernel efficiently and accurately. This then permits the fast evaluation of the desired convolution with a source distribution sampled on an anisotropic, tensor-product grid. For problems in d dimensions, the storage cost is O(2^d N) independent of the aspect ratio, and the computational cost is 0(2^d N log(2^d N)), where N is the total number of grid points needed to resolve the density. The performance of the algorithm is illustrated with several examples.