Fast convolution with radial kernels at nonequispaced knots

We develop a new algorithm for the fast evaluation of linear combinations of radial functions f (y(j)) := Sigma(k=1)(N) alpha(k) K(parallel toy(j) - x(k)parallel to) (j = 1,..., M) for x(k), y(j) is an element of R-2 based on the recently developed fast Fourier transform at nonequispaced knots. For smooth kernels, e.g. the Gaussian, our algorithm requires O(N + M) arithmetic operations. In case of singular kernels an additional regularization procedure must be incorporated and the algorithm has the arithmetic complexity O(N log rootN + M) or O(M log rootM + N) if either the points yj 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.