Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



Efficient computation of the Fourier transform on finite groups

Authors: Persi Diaconis and Daniel Rockmore
Journal: J. Amer. Math. Soc. 3 (1990), 297-332
MSC: Primary 20C40; Secondary 20B40, 20C30, 68Q25
MathSciNet review: 1030655
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC: 20C40, 20B40, 20C30, 68Q25

Retrieve articles in all journals with MSC: 20C40, 20B40, 20C30, 68Q25

Additional Information

Article copyright: © Copyright 1990 American Mathematical Society