Journal of the American Mathematical Society
Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.
The 2020 MCQ for Journal of the American Mathematical Society is 4.79.
Journals Home eContent Search About JAMS Editorial Board Author and Submission Information Journal Policies Subscription Information
Efficient computation of the Fourier transform on finite groups
by Persi Diaconis and Daniel Rockmore PDF
J. Amer. Math. Soc. 3 (1990), 297-332 Request permission
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 | G \right |^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$.
Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592
Richard Askey and Amitai Regev, Maximal degrees for Young diagrams in a strip, European J. Combin. 5 (1984), no. 3, 189–191. MR 765624, DOI 10.1016/S0195-6698(84)80001-3
M. D. Atkinson, The complexity of group algebra computations, Theoret. Comput. Sci. 5 (1977/78), no. 2, 205–209. MR 483650, DOI 10.1016/0304-3975(77)90007-X
L. Auslander and R. Tolimieri, Is computing with the finite Fourier transform pure or applied mathematics?, Bull. Amer. Math. Soc. (N.S.) 1 (1979), no. 6, 847–897. MR 546312, DOI 10.1090/S0273-0979-1979-14686-X
László Babai, On the length of subgroup chains in the symmetric group, Comm. Algebra 14 (1986), no. 9, 1729–1736. MR 860123, DOI 10.1080/00927878608823393
L. Babai and L. Rónyai (1989), Computing irreducible representations of finite groups, Technical report, computer science dept. University of Chicago.
Thomas Beth, Verfahren der schnellen Fourier-Transformation, Leitfäden der Angewandten Mathematik und Mechanik [Guides to Applied Mathematics and Mechanics], vol. 61, B. G. Teubner, Stuttgart, 1984 (German). Die allgemeine diskrete Fourier-Transformation—ihre algebraische Beschreibung, Komplexität und Implementierung [The general discrete Fourier transform—its algebraic description, complexity and implementation]; Teubner Studienbücher Informatik. [Teubner Textbooks in Computer Science]. MR 753642
Thomas Beth, On the computational complexity of the general discrete Fourier transform, Theoret. Comput. Sci. 51 (1987), no. 3, 331–339. MR 909461, DOI 10.1016/0304-3975(87)90041-7
Laura Chihara, On the zeros of the Askey-Wilson polynomials, with applications to coding theory, SIAM J. Math. Anal. 18 (1987), no. 1, 191–207. MR 871831, DOI 10.1137/0518015
Michael Clausen, Fast Fourier transforms for metabelian groups, SIAM J. Comput. 18 (1989), no. 3, 584–593. MR 996838, DOI 10.1137/0218040
Michael Clausen, Fast generalized Fourier transforms, Theoret. Comput. Sci. 67 (1989), no. 1, 55–63. MR 1015084, DOI 10.1016/0304-3975(89)90021-2
A. J. Coleman, Induced representations with applications to $S_{n}$ and $\textrm {GL}(n)$, Queen's Papers in Pure and Applied Mathematics, No. 4, Queen's University, Kingston, Ont., 1966. Lecture notes prepared by C. J. Bradley. MR 0202859
James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297–301. MR 178586, DOI 10.1090/S0025-5718-1965-0178586-1
D. Coppersmith and S. Winograd (1987), Matrix multiplication via arithmetic progressions, Proc. 19th ACM Sympos. on the Theory of Computing (STOC), pp. 1-6.
Persi Diaconis, Average running time of the fast Fourier transform, J. Algorithms 1 (1980), no. 2, 187–208. MR 604863, DOI 10.1016/0196-6774(80)90022-X
Persi Diaconis, A generalization of spectral analysis with application to ranked data, Ann. Statist. 17 (1989), no. 3, 949–979. MR 1015133, DOI 10.1214/aos/1176347251
Persi Diaconis, Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR 964069
Persi Diaconis and R. L. Graham, The Radon transform on $Z^k_2$, Pacific J. Math. 118 (1985), no. 2, 323–345. MR 789174
Persi Diaconis and Mehrdad Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159–179. MR 626813, DOI 10.1007/BF00535487
J. Driscoll and D. Healy (1989), A symptotically fast algorithms for spherical and related transforms, Technical report, Dept. of Math. and computer Sci., Dartmouth College. P. Edelman and D. White (1988), Codes, transforms, and the spectrum of the symmetric group, Paper 231, presented at AMS Atlanta meetings.
Douglas F. Elliott and K. Ramamohan Rao, Fast transforms, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, 1982. Algorithms, analyses, applications. MR 696936
A. Garsia and T. McLarnan (1986), Relations between Young's natural and the Kazhdan-Lusztig representations of ${S_n}$, Technical report, Department of Mathematics, Univ. of California, San Diego.
Herman H. Goldstine, A history of numerical analysis from the 16th through the 19th century, Studies in the History of Mathematics and Physical Sciences, Vol. 2, Springer-Verlag, New York-Heidelberg, 1977. MR 0484905
I. J. Good, The interaction algorithm and practical Fourier analysis, J. Roy. Statist. Soc. Ser. B 20 (1958), 361–372. MR 102888
I. J. Good, Analogues of Poisson's summation formula, Amer. Math. Monthly 69 (1962), 259–266. MR 184006, DOI 10.2307/2312938
W. D. Hillis (1985), The connection machine, MIT Press, Cambridge, Mass.
G. D. James, The representation theory of the symmetric groups, Lecture Notes in Mathematics, vol. 682, Springer, Berlin, 1978. MR 513828
Gordon James and Adalbert Kerber, The representation theory of the symmetric group, Encyclopedia of Mathematics and its Applications, vol. 16, Addison-Wesley Publishing Co., Reading, Mass., 1981. With a foreword by P. M. Cohn; With an introduction by Gilbert de B. Robinson. MR 644144
Adalbert Kerber, Representations of permutation groups. I, Lecture Notes in Mathematics, Vol. 240, Springer-Verlag, Berlin-New York, 1971. MR 0325752
Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Advances in Math. 26 (1977), no. 2, 206–222. MR 1417317, DOI 10.1016/0001-8708(77)90030-5
Daniel Rockmore, Fast Fourier analysis for abelian group extensions, Adv. in Appl. Math. 11 (1990), no. 2, 164–204. MR 1053228, DOI 10.1016/0196-8858(90)90008-M
Gian-Carlo Rota (ed.), Probability, statistical mechanics, and number theory, Advances in Mathematics, Supplementary Studies, vol. 9, Academic Press, Inc., Orlando, FL, 1986. A volume dedicated to Mark Kac. MR 875441
Amitai Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. in Math. 41 (1981), no. 2, 115–136. MR 625890, DOI 10.1016/0001-8708(81)90012-8
Daniel Rockmore, Computation of Fourier transforms on the symmetric group, Computers and mathematics (Cambridge, MA, 1989) Springer, New York, 1989, pp. 156–165. MR 1005972
—(1989), Fast Fourier inversion for finite groups technical report, Dept. of Math. Columbia Univ.
Oscar Rothaus and John G. Thompson, A combinatorial problem in the symmetric group, Pacific J. Math. 18 (1966), 175–178. MR 195934
Jean-Pierre Serre, Linear representations of finite groups, Graduate Texts in Mathematics, Vol. 42, Springer-Verlag, New York-Heidelberg, 1977. Translated from the second French edition by Leonard L. Scott. MR 0450380
Dennis Stanton, Orthogonal polynomials and Chevalley groups, Special functions: group theoretical aspects and applications, Math. Appl., Reidel, Dordrecht, 1984, pp. 87–128. MR 774056
A. M. Vershik and S. V. Kerov, Asymptotic theory of the characters of a symmetric group, Funktsional. Anal. i Prilozhen. 15 (1981), no. 4, 15–27, 96 (Russian). MR 639197
—(1985), Asymptotics of the largest and typical dimensions of the irreducible representations of a symmetric group, Functional Anal. Appl. 19, 21-31.
S. Winograd, On computing the discrete Fourier transform, Math. Comp. 32 (1978), no. 141, 175–199. MR 468306, DOI 10.1090/S0025-5718-1978-0468306-4
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
Journal: J. Amer. Math. Soc. 3 (1990), 297-332
MSC: Primary 20C40; Secondary 20B40, 20C30, 68Q25