×

zbMATH — the first resource for mathematics

Efficient computation of the Fourier transform on finite groups. (English) Zbl 0709.65125
The Fourier transform FT of a function f on a finite group is defined as \(\hat f(\rho)= \sum_{s\in G}f(s) \rho(s)\) at an irreducible representation \(\rho\). Direct computation for all irreducible representations involves order \(| G|^ 2\) arithmetic operations in principle. This paper derives fast algorithms for the FT on symmetric group \(S_ n\). There \((n!)^ 2\) is reduced to \(n(n!)^{a/2}\) with the constant a for the matrix multiplication. The discussion refers to parallelizability in this implementation and to the inverse transform.
Reviewer: Y.Kobayashi

MSC:
65T50 Numerical methods for discrete and fast Fourier transforms
65F30 Other matrix algorithms (MSC2010)
65J10 Numerical solutions to equations with linear operators
20C15 Ordinary representations and characters
43A65 Representations of groups, semigroups, etc. (aspects of abstract harmonic analysis)
PDF BibTeX Cite
Full Text: DOI
References:
[1] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0326.68005
[2] Richard Askey and Amitai Regev, Maximal degrees for Young diagrams in a strip, European J. Combin. 5 (1984), no. 3, 189 – 191. · Zbl 0555.05009
[3] M. D. Atkinson, The complexity of group algebra computations, Theoret. Comput. Sci. 5 (1977/78), no. 2, 205 – 209. · Zbl 0368.20005
[4] 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. · Zbl 0475.42014
[5] László Babai, On the length of subgroup chains in the symmetric group, Comm. Algebra 14 (1986), no. 9, 1729 – 1736. · Zbl 0604.20004
[6] L. Babai and L. Rónyai (1989), Computing irreducible representations of finite groups, Technical report, computer science dept. University of Chicago.
[7] 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]. · Zbl 0536.65098
[8] Thomas Beth, On the computational complexity of the general discrete Fourier transform, Theoret. Comput. Sci. 51 (1987), no. 3, 331 – 339. · Zbl 0629.68041
[9] 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. · Zbl 0611.33013
[10] Michael Clausen, Fast Fourier transforms for metabelian groups, SIAM J. Comput. 18 (1989), no. 3, 584 – 593. · Zbl 0677.68028
[11] Michael Clausen, Fast generalized Fourier transforms, Theoret. Comput. Sci. 67 (1989), no. 1, 55 – 63. · Zbl 0677.65143
[12] A. J. Coleman, Induced representations with applications to \?_{\?} and \?\?(\?), Lecture notes prepared by C. J. Bradley. Queen’s Papers in Pure and Applied Mathematics, No. 4, Queen’s University, Kingston, Ont., 1966. · Zbl 0141.02503
[13] James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297 – 301. · Zbl 0127.09002
[14] D. Coppersmith and S. Winograd (1987), Matrix multiplication via arithmetic progressions, Proc. 19th ACM Sympos. on the Theory of Computing (STOC), pp. 1-6. · Zbl 0702.65046
[15] Persi Diaconis, Average running time of the fast Fourier transform, J. Algorithms 1 (1980), no. 2, 187 – 208. · Zbl 0445.68029
[16] Persi Diaconis, A generalization of spectral analysis with application to ranked data, Ann. Statist. 17 (1989), no. 3, 949 – 979. · Zbl 0688.62005
[17] 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. · Zbl 0695.60012
[18] Persi Diaconis and R. L. Graham, The Radon transform on \?^{\?}\(_{2}\), Pacific J. Math. 118 (1985), no. 2, 323 – 345. · Zbl 0581.43001
[19] Persi Diaconis and Mehrdad Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159 – 179. · Zbl 0485.60006
[20] 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.
[21] P. Edelman and D. White (1988), Codes, transforms, and the spectrum of the symmetric group, Paper 231, presented at AMS Atlanta meetings.
[22] Douglas F. Elliott and K. Ramamohan Rao, Fast transforms, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, 1982. Algorithms, analyses, applications. · Zbl 0562.65097
[23] 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. · Zbl 0657.20014
[24] Herman H. Goldstine, A history of numerical analysis from the 16th through the 19th century, Springer-Verlag, New York-Heidelberg, 1977. Studies in the History of Mathematics and Physical Sciences, Vol. 2. · Zbl 0402.01005
[25] I. J. Good, The interaction algorithm and practical Fourier analysis, J. Roy. Statist. Soc. Ser. B 20 (1958), 361 – 372. · Zbl 0086.12403
[26] I. J. Good, Analogues of Poisson’s summation formula, Amer. Math. Monthly 69 (1962), 259 – 266. · Zbl 0106.02502
[27] W. D. Hillis (1985), The connection machine, MIT Press, Cambridge, Mass.
[28] G. D. James, The representation theory of the symmetric groups, Lecture Notes in Mathematics, vol. 682, Springer, Berlin, 1978. · Zbl 0393.20009
[29] 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. · Zbl 0491.20010
[30] Adalbert Kerber, Representations of permutation groups. I, Lecture Notes in Mathematics, Vol. 240, Springer-Verlag, Berlin-New York, 1971. · Zbl 0232.20014
[31] Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0357.68001
[32] Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0357.68001
[33] B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Advances in Math. 26 (1977), no. 2, 206 – 222. · Zbl 0363.62068
[34] Daniel Rockmore, Fast Fourier analysis for abelian group extensions, Adv. in Appl. Math. 11 (1990), no. 2, 164 – 204. · Zbl 0709.65126
[35] Gian-Carlo Rota , 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.
[36] Amitai Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. in Math. 41 (1981), no. 2, 115 – 136. · Zbl 0509.20009
[37] Daniel Rockmore, Computation of Fourier transforms on the symmetric group, Computers and mathematics (Cambridge, MA, 1989) Springer, New York, 1989, pp. 156 – 165. · Zbl 0679.20010
[38] -(1989), Fast Fourier inversion for finite groups technical report, Dept. of Math. Columbia Univ.
[39] Oscar Rothaus and John G. Thompson, A combinatorial problem in the symmetric group, Pacific J. Math. 18 (1966), 175 – 178. · Zbl 0145.02905
[40] Jean-Pierre Serre, Linear representations of finite groups, Springer-Verlag, New York-Heidelberg, 1977. Translated from the second French edition by Leonard L. Scott; Graduate Texts in Mathematics, Vol. 42. · Zbl 0355.20006
[41] Dennis Stanton, Orthogonal polynomials and Chevalley groups, Special functions: group theoretical aspects and applications, Math. Appl., Reidel, Dordrecht, 1984, pp. 87 – 128. · Zbl 0578.20041
[42] 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). · Zbl 0534.20008
[43] -(1985), Asymptotics of the largest and typical dimensions of the irreducible representations of a symmetric group, Functional Anal. Appl. 19, 21-31. · Zbl 0592.20015
[44] S. Winograd, On computing the discrete Fourier transform, Math. Comp. 32 (1978), no. 141, 175 – 199. · Zbl 0374.68034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.