Efficient computation of the Fourier transform on finite groups

Let $G$ be a finite group, $f:G \to {\mathbf{C}}$ a function, and $\rho$ an irreducible representation of $G$. The Fourier transform is defined as $\hat f(\rho ) = {\Sigma _{s \in G}}f(s)\rho (s)$. Direct computation for all irreducible representations involves order ${\left\vert G \right\vert^2}$ operations. We derive fast algorithms and develop them for the symmetric group ${S_n}$. There, ${(n!)^2}$ is reduced to $n{(n!)^{a/2}}$, where $a$ is the constant for matrix multiplication (2.38 as of this writing). Variations of the algorithm allow efficient computation for ``small'' representations. A practical version of the algorithm is given on ${S_n}$. Numerical evidence is presented to show a speedup by a factor of 100 for $n = 9$.