FFTs on the Rotation Group

We discuss an implementation of an efficient algorithm for the numerical computation of Fourier transforms of bandlimited functions defined on the rotation group SO(3). The implementation is freely available on the web. The algorithm described herein uses O(B ⁴) operations to compute the Fourier coefficients of a function whose Fourier expansion uses only (the O(B ³)) spherical harmonics of degree at most B. This compares very favorably with the direct O(B ⁶) algorithm derived from a basic quadrature rule on O(B ³) sample points. The efficient Fourier transform also makes possible the efficient calculation of convolution over SO(3) which has been used as the analytic engine for some new approaches to searching 3D databases (Funkhouser et al., ACM Trans. Graph. 83–105, 2003]; Kazhdan et al., Eurographics Symposium in Geometry Processing, pp. 167–175, 2003]). Our implementation is based on the “Separation of Variables” technique (see, e.g., Maslen and Rockmore, Proceedings of the DIMACS Workshop on Groups and Computation, pp. 183–237, 1997]). In conjunction with techniques developed for the efficient computation of orthogonal polynomial expansions (Driscoll et al., SIAM J. Comput. 26(4):1066–1099, 1997]), our fast SO(3) algorithm can be improved to give an algorithm of complexity O(B ³log ² 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. First author was supported by NSF ITR award; second author was supported by NSF Grant 0219717 and the Santa Fe Institute.