Efficient computation of the Fourier transform on finite groups

Diaconis, Persi; Rockmore, Daniel

doi:10.1090/S0894-0347-1990-1030655-4

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

Computing irreducible representations of finite groups

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

Matrix multiplication via arithmetic progressions

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

A symptotically fast algorithms for spherical and related transforms

Codes, transforms, and the spectrum of the symmetric group

Douglas F. Elliott and K. Ramamohan Rao, Fast transforms, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, 1982. Algorithms, analyses, applications. MR 696936

Relations between Young’s natural and the Kazhdan-Lusztig representations of

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

The connection machine

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

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

Asymptotics of the largest and typical dimensions of the irreducible representations of a symmetric group

19

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