Volume 23, pp. 263-287, 2006.

Fast multilevel evaluation of smooth radial basis function expansions

Oren E. Livne and Grady B. Wright

Abstract

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)\log (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 de-blurring of images, and particle force summation.

Full Text (PDF) [407 KB], BibTeX

Key words

Radial basis functions, fast multilevel multi-summation, integral transforms, particle interaction

AMS subject classifications

41A21, 41A30, 41A63, 65D25, 65N06, 65R10, 68Q25