FFTs for the 2-sphere-improvements and variations (Q1416654)

This very interesting paper is a continuation of the work of \textit{J. R. Driscoll} and \textit{D. M. Healy jun.} [Adv. Appl. Math. 15, 202--250 (1994; Zbl 0801.65141)]. The authors present a comprehensive reformulation of the original fast algorithm of the discrete spherical Fourier transform which results in an improved inverse transform and consequent improved convolution algorithm for band-limited functions. The problem of computing fast discrete spherical Fourier transforms is reduced to the efficient calculation of discrete Legendre transforms. Fast discrete Legendre transforms are obtained by two basic ideas: (1) using the Legendre recurrence, (2) smoothing and subsampling of data vectors via discrete cosine transforms. Fast algorithms of the discrete spherical Fourier transform, the corresponding inverse transform and convolution require at most \(O(N(\log N)^2)\) operations, where \(N\) is the number of sample points. The authors address implementation considerations and give heuristics for allowing reliable and computationally efficient floating point implementations of slightly modified algorithms. These claims are supported by extensive numerical experiments from the implementation in C on DEC, HP, SGI and Linux Pentium platforms. These results indicate that these algorithms are both reliable and efficient for a large range of useful problem sizes. Finally, two applications (computation of the bispectrum for band-limited functions, matched filtering of signals on the sphere) are sketched.