Efficient computation of Fourier transforms on compact groups (Q1271501)

The paper describes a fast Fourier transform algorithm for the computation of Fourier transforms on compact Lie groups. For a given compact Lie group \(G\), a finite subset \(X\) of \(G\), a finite set \(R\) of finite dimensional representations of \(G\), and a complex valued function \(f\) on \(X\), the aim is to efficiently compute \[ F(\rho)=\sum_xx\in Xf(x)\rho(x) \] for all \(\rho\in R\). For each positive integer \(b\), let \(R=R_b\) denote the set of irreducible unitary representations of \(G\) that have highest weight with norm at most \(b\). Subsets \(X=X_b\) are defined of the classical groups for which the above calculation may be performed relative to Gel'fand-Tsetlin bases in \(O(b^{\dim G+\gamma(G)})\) operations, where \(\gamma(G)\) depends on the classical group in question. Finally, analogous computations are considered on homogeneous spaces, and for finite sets \(R=D\) of distributions.