Fast convolution with radial kernels at nonequispaced knots (Q1882396)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Fast convolution with radial kernels at nonequispaced knots
scientific article

    Statements

    Fast convolution with radial kernels at nonequispaced knots (English)
    0 references
    0 references
    0 references
    0 references
    1 October 2004
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    fast Fourier transform
    0 references
    nonequispaced knots
    0 references
    fast summation
    0 references
    fast multipole method
    0 references
    fast Gauss transform
    0 references
    thinplate spline approximation
    0 references
    scattered data approximation
    0 references
    radial basis function
    0 references
    error estimates
    0 references
    regularization
    0 references
    numerical examples
    0 references
    algorithm
    0 references
    0 references
    0 references
    0 references
    0 references