Fast convolution with radial kernels at nonequispaced knots
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.
- scientific article; zbMATH DE number 733432
- Fast discrete convolution in \(\mathbb{R}^2\) with radial kernels using non-uniform fast Fourier transform with nonequispaced frequencies
- A kernel independent fast multipole algorithm for radial basis functions
- A fast algorithm for convolution integrals with space and time variant kernels
- Radial kernels via scale derivatives
- Convolution kernels based on thin-plate splines
- Fast and exact projected convolution for non-equidistant grids
- Convolution Operators for Radial Basis Approximation
- scientific article; zbMATH DE number 1361571
- Fast Convolution for Nonreflecting Boundary Conditions
- A fast algorithm for filtering and wavelet decomposition on the sphere
- A fast algorithm for particle simulations
- A matrix version of the fast multipole method
- A new version of the fast Gauss transform
- A note on fast Fourier transforms for nonequispaced grids
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- An Improved Fast Multipole Algorithm for Potential Fields on the Line
- Application of the fast Gauss transform to option pricing
- Fast evaluation of radial basis functions: Methods for generalized multiquadrics in R^n
- Fast evaluation of radial basis functions: methods for two-dimensional polyharmonic splines
- Fast Evaluation of Radial Basis Functions: Moment-Based Methods
- Fast Fourier Transforms for Nonequispaced Data
- Fast Summation at Nonequispaced Knots by NFFT
- scientific article; zbMATH DE number 46317 (Why is no real title available?)
- scientific article; zbMATH DE number 1126864 (Why is no real title available?)
- scientific article; zbMATH DE number 1373505 (Why is no real title available?)
- Matrix-free iterative solution strategies for large dense linear systems
- Mosaic-skeleton approximations
- On the fast Fourier transform of functions with singularities
- On the fast matrix multiplication in the boundary element method by panel clustering
- Spectral approximation of the free-space heat kernel
- The Fast Gauss Transform
- Adaptive cross-approximation for surface reconstruction using radial basis functions
- Convolution kernels based on thin-plate splines
- A discrete adapted hierarchical basis solver for radial basis function interpolation
- Computing the survival probability density function in jump-diffusion models: a new approach based on radial basis functions
- Learning in high-dimensional feature spaces using ANOVA-based fast matrix-vector multiplication
- Accelerating the calculation of dipolar interactions in particle based simulations with open boundary conditions by means of the P\(^{2}\)NFFT method
- Fast discrete convolution in \(\mathbb{R}^2\) with radial kernels using non-uniform fast Fourier transform with nonequispaced frequencies
- On certain (block) Toeplitz matrices related to radial functions
- Fast and exact projected convolution for non-equidistant grids
- A high-order, analytically divergence-free approximation method for the time-dependent Stokes problem
- Consistency of variational continuous-domain quantization via kinetic theory
- Non-uniform FFT for the finite element computation of the micromagnetic scalar potential
- Fast summation based on fast trigonometric transforms at non‐equispaced nodes
- Faster fast evaluation of thin plate splines in two dimensions
- Fast Summation at Nonequispaced Knots by NFFT
- A fast algorithm for the convolution of functions with compact support using Fourier extensions
- Spectral analysis and preconditioning techniques for radial basis function collocation matrices.
- Semi-supervised Learning for Aggregated Multilayer Graphs Using Diffuse Interface Methods and Fast Matrix-Vector Products
- Fast One-Dimensional Convolution with General Kernels Using Sum-of-Exponential Approximation
- A Fourier Extension Based Numerical Integration Scheme for Fast and High-Order Approximation of Convolutions with Weakly Singular Kernels
- Fast NFFT based summation of radial functions
- Fast Gauss transforms with complex parameters using NFFTs
- Fast kernel summation in high dimensions via slicing and Fourier transforms
- A lightweight, geometrically flexible fast algorithm for the evaluation of layer and volume potentials
- Efficient nonlocal linear image denoising: bilevel optimization with nonequispaced fast Fourier transform and matrix-free preconditioning
- Slicing of radial functions: a dimension walk in the Fourier space
- A dual-space multilevel kernel-splitting framework for discrete and continuous convolution
- Fast evaluation of additive kernels: feature arrangement, Fourier methods, and kernel derivatives
- Fast ewald summation based on NFFT with mixed periodicity
- Fast summation of Stokes potentials using a new kernel-splitting in the DMK framework
- The sparse cardinal sine decomposition and its application for fast numerical convolution
- The uselessness of the fast Gauss transform for summing Gaussian radial basis function series
- The GLT class as a generalized Fourier analysis and applications
This page was built for publication: Fast convolution with radial kernels at nonequispaced knots
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1882396)
