Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
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

DOI: http://dx.doi.org/10.1090/S0894-0347-1990-1030655-4
PII: S 0894-0347(1990)1030655-4
Article copyright: © Copyright 1990 American Mathematical Society