TY - JOUR

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

AU - Greengard, Leslie

AU - Jiang, Shidong

AU - Zhang, Yong

N1 - Publisher Copyright:
© 2018 Society for Industrial and Applied Mathematics.

PY - 2018/1

Y1 - 2018/1

N2 - 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(2d N) independent of the aspect ratio, and the computational cost is 0(2d N log(2d 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.

AB - 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(2d N) independent of the aspect ratio, and the computational cost is 0(2d N log(2d 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.

KW - Anisotropic density

KW - Fft

KW - Green's function

KW - Sum-of-Gaussians approximation

KW - Truncated kernel method

UR - http://www.scopus.com/inward/record.url?scp=85060028485&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85060028485&partnerID=8YFLogxK

U2 - 10.1137/18M1184497

DO - 10.1137/18M1184497

M3 - Article

AN - SCOPUS:85060028485

SN - 1064-8275

VL - 40

SP - A3733-A3754

JO - SIAM Journal on Scientific Computing

JF - SIAM Journal on Scientific Computing

IS - 6

ER -