Efficient computation of Fourier transforms on compact groups

This article genralizes the fast Fourier transform algorithm to the computation of Fourier transforms on compact Lie groups. The basic technique uses factorization of group elements and Gel'fand-Tsetlin bases to simplify the computations, and may be extended to treat the computation of Fourier transforms of finitely supported distributions on the group. Similar transforms may be defined on homogeneous spaces; in that case we show how special function properties of spherical functions lead to more efficient algorithms. These results may all be viewed as generalizations of the fast Fourier transform algorithms on the circle, and of recent results about Fourier transforms on finite groups. Acknowledgements and Notes. This paper was written while the author was supported by the Max-Planck-Institut für Mathematik, Bonn, Germany.