Springe zum Hauptinhalt
Fakultät für Mathematik
Fakultät für Mathematik
Keiner, Jens; Kunis, Stefan; Potts, Daniel : Fast summation of radial functions on the sphere

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