Volume 16, pp. 70-93, 2003.

A fast algorithm for filtering and wavelet decomposition on the sphere

Martin Böhme and Daniel Potts


This paper introduces a new fast algorithm for uniform-resolution filtering of functions defined on the sphere. We use a fast summation algorithm based on Nonequispaced Fast Fourier Transforms, building on previous work that used Fast Multipole Methods. The resulting algorithm performs a triangular truncation of the spectral coefficients while avoiding the need for fast spherical Fourier transforms. The method requires ${\cal O}(N^2\log N)$ operations for ${\cal O}(N^2)$ grid points. Furthermore, we apply these techniques to obtain a fast wavelet decomposition algorithm on the sphere. We present the results of numerical experiments to illustrate the performance of the algorithms.

Full Text (PDF) [540 KB], BibTeX

Key words

spherical filter, spherical Fourier transform, spherical harmonics, associated Legendre functions, fast discrete transforms, fast Fourier transform at nonequispaced knots, wavelets, fast discrete summation.

AMS subject classifications

65Txx, 33C55, 42C10.

< Back