Livne, Oren E.; Wright, Grady B. Fast multilevel evaluation of smooth radial basis function expansions. (English) Zbl 1112.65012 ETNA, Electron. Trans. Numer. Anal. 23, 263-287 (2006). Summary: Radial basis functions (RBFs) are a powerful tool for interpolating/approximating multidimensional scattered data. Notwithstanding, RBFs pose computational challenges, such as the efficient evaluation of an \(n\)-center RBF expansion at \(m\) points. A direct summation requires \(O(nm)\) operations. We present a new multilevel method whose cost is only \(O((n+m) \ln(1/\delta)^d)\), where \(\delta\) is the desired accuracy and \(d\) is the dimension. The method applies to smooth radial kernels, e.g., Gaussian, multiquadric, or inverse multiquadric. We present numerical results, discuss generalizations, and compare our method to other fast RBF evaluation methods. This multilevel summation algorithm can be also applied beyond RBFs, to discrete integral transform evaluation, Gaussian filtering and deblurring of images, and particle force summation. Cited in 4 Documents MSC: 65D15 Algorithms for approximation of functions 65B10 Numerical summation of series 41A30 Approximation by other special function classes 41A63 Multidimensional problems 65R10 Numerical methods for integral transforms Keywords:scattered data approximation; fast multilevel multi-summation; integral transforms; particle interaction; multilevel method; numerical results; Gaussian filtering PDFBibTeX XMLCite \textit{O. E. Livne} and \textit{G. B. Wright}, ETNA, Electron. Trans. Numer. Anal. 23, 263--287 (2006; Zbl 1112.65012) Full Text: EuDML Link