Computing Fourier transforms and convolutions on the 2-sphere (Q1330934)

This important paper deals with the efficient computation of the spherical harmonic expansion, or Fourier transform, of functions defined on the unit sphere \(S^ 2\). For example, the Fourier transform on \(S^ 2\) appears in tomography, geophysics, seismology, atmospheric science, and crystallography. The known Fourier analysis on \(S^ 2\) is used to prove a sampling theorem for band-limited functions. This sampling theorem allows the exact computation of the Fourier transforms of a band- limited function as finite sums of sampled data at an equiangular grid. In order to construct an efficient scheme for evaluating these sums, the authors describe an \(O(n( \log n)^ 2)\) time algorithm for the Legendre polynomial transform of a function sampled at the \(n = 2^ k\) nodes \(\cos (2 \pi j/n)\) \((j = 0, \dots, n - 1)\). Theoretical and experimental results concerning the effect of finite precision arithmetic on this algorithm are described, too. Finally, the procedure is extended to the associated Legendre functions to obtain a fast algorithm of the Fourier transforms on \(S^ 2\).