Fast convolution with radial kernels at nonequispaced knots

摘要

We develop a new algorithm for the fast evaluation of linear combinations of radial functions based on the recently developed fast Fourier transform at nonequispaced knots. For smooth kernels, e.g. the Gaussian, our algorithm requires arithmetic operations. In case of singular kernels an additional regularization procedure must be incorporated and the algorithm has the arithmetic complexity if either the points y j or the points x k are “reasonably uniformly distributed”. We prove error estimates to obtain clues about the choice of the involved parameters and present numerical examples for various singular and smooth kernels in two dimensions.