Fast convolution with radial kernels at nonequispaced knots (Q1882396)

Let \(K\) be a real function and \(\| x\|\) denotes the Euclidean norm of \(x\in\mathbb{R}^2\). This interesting paper is the continuation of \textit{D. Potts} and \textit{G. Steidl} [SIAM J. Sci. Comput. 24, No. 6, 2013--2037 (2003; Zbl 1040.65110)] and presents a new fast algorithm for the approximative evaluation of the sums \[ f(y_j)=\sum^N_{k=1} \alpha_k K\bigl(\| y_j-x_k \|\bigr)\quad (j=1,\dots,M) \] with given \(x_k\), \(y_j\in\mathbb{R}^2\) and \(\alpha_k\in\mathbb{R}\). The above sums are interpreted as a modified convolution and diagonalized by a fast Fourier transform at nonequispaced knots [see \textit{A. Dutt} and \textit{V. Rokhlin}, SIAM J. Sci. Comput. 14, No. 6, 1368--1393 (1993; Zbl 0791.65108) and \textit{G. Steidl}, Adv. Comput. Math. 9, No. 3--4, 337--352 (1998; Zbl 0917.65123)]. This new algorithm is a good alternative to the fast multipole method (with \(K(t)=\log t)\) of \textit{L. Greengard} and \textit{V. Rokhlin} [J. Comput. Phys. 73, 325--348 (1987; Zbl 0629.65005)] and the fast Gauss transform (with \(K(t)=\exp(-\sigma t^2))\) of \textit{L. Greengard} and \textit{J. Strain} [SIAM J. Sci. Stat. Comput. 12, 79--94 (1991; Zbl 0721.65081)]. For a smooth function \(K(t)\) (as \(\exp(-\sigma t^2))\), this new algorithm requires \(O(N+M)\) flops. For a singular function \(K(t)\) (as \(\log| t|\) or \(t^2\log| t|)\), this method contains an additional regularization procedure and requires \(O(N \log\sqrt N+M)\) or \(O(M\log\sqrt M+N)\) flops if either \(y_j\) or \(x_k\) are reasonably uniformly distributed. Useful error estimates and numerical examples are presented.