Keiner, Jens ; Kunis, Stefan ; Potts, Daniel : Fast summation of radial functions on the sphere

Author(s):

Keiner, Jens
Kunis, Stefan
Potts, Daniel

Title:

Fast summation of radial functions on the sphere

Electronic source:

application/postscript

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 17, 2005

Mathematics Subject Classification:

65T50			[ Discrete and fast Fourier transforms ]
65F30			[ Other matrix algorithms ]
42C10			[ Fourier series in special orthogonal functions ]
33C55			[ Spherical harmonics ]
15A23			[ Factorization of matrices ]

Abstract:

Radial functions are a powerful tool in many areas of multi-dimensional approximation, especially when dealing with scattered data. We present a fast approximate algorithm for the evaluation of linear combinations of radial functions on the sphere $\mathbb{S}^2$. The approach is based on a particular rank approximation of the corresponding Gram matrix and fast algorithms for spherical Fourier transforms. The proposed method takes $\mathcal{O}(L)$ arithmetic operations for $L$ arbitrarily distributed nodes on the sphere. In contrast to other methods, we do not require the nodes to be sorted or pre-processed in any way, thus the pre-computation effort only depends on the particular radial function and the desired accuracy. We establish explicit error bounds for a range of radial functions and provide numerical examples covering approximation quality, speed measurements, and a comparison of our particular matrix approximation with a truncated singular value decomposition.

Keywords:

Fast discrete summation, Radial basis functions, Zonal functions, FFT, NFFT

Language:

English

Publication time:

10 / 2005