×

Fast multilevel evaluation of smooth radial basis function expansions. (English) Zbl 1112.65012

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.

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
PDFBibTeX XMLCite
Full Text: EuDML Link