FFTs on the rotation group (Q2483008)

An implementation is given of an algorithm for the numerical computation of Fourier transforms of band limited functions defined on the rotation group \(\text{SO}(3)\). The algorithm described herein uses \(\text{O}(B)\) operations to compute the Fourier coefficients of a function whose Fourier expansion uses only (the \(\text{O}(B^3)\)) spherical harmonics of degree at most \(B\). This compares very favourably with the direct \(\text{O}(B^6)\) algorithm derived from a basic quadrature rule on \(\text{O}(B^3)\) sample points. The efficient Fourier transform also makes possible the efficient calculation of convolution over \(\text{SO}(3)\) which has been used as the analytic engine for some new approaches to searching 3D databases: \textit{Funkhouser} et al. [ACM Trans Graph. 83--105 (2003)]; \textit{Kazhdan} et al. [Eurographics Symposium in Geometry Processing, 167--175 (2003)]. The implementation is based on the ``Separation of variables'' of \textit{D. K. Maslen} and \textit{D. N. Rockmore} [Workshop on groups and computation, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 28, 183--237 (1997; Zbl 0892.20008)]. In conjunction with the techniques developed for the efficient computation of orthogonal polynomial expansions by \textit{J. R. Driscoll}, \textit{D. J. Healy jun.} and \textit{D. N. Rockmore} [SIAM J. Comput. 26, No. 4, 1066--1099 (1997; Zbl 0896.65094)], the fast \(\text{SO}(3)\) algorithm can be improved to give an algorithm of complexity \(O(B^3\log^2 B)\), but at a cost in numerical reliability. Numerical and empirical results are presented establishing the empirical stability of the basic algorithm. Examples of applications are presented as well.