Efficient computation of the Fourier transform on finite groups
HTML articles powered by AMS MathViewer
- by Persi Diaconis and Daniel Rockmore
- J. Amer. Math. Soc. 3 (1990), 297-332
- DOI: https://doi.org/10.1090/S0894-0347-1990-1030655-4
- PDF | Request permission
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 | 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$.References
- 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
- 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
Bibliographic Information
- © Copyright 1990 American Mathematical Society
- Journal: J. Amer. Math. Soc. 3 (1990), 297-332
- MSC: Primary 20C40; Secondary 20B40, 20C30, 68Q25
- DOI: https://doi.org/10.1090/S0894-0347-1990-1030655-4
- MathSciNet review: 1030655