Fast multilevel evaluation of smooth radial basis function expansions

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/δ)^d), where δ 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.