The efficient computation of Fourier transforms on the symmetric group

Maslen, David

doi:10.1090/S0025-5718-98-00964-8

The efficient computation of Fourier transforms on the symmetric group
HTML articles powered by AMS MathViewer

by David K. Maslen PDF

Math. Comp. 67 (1998), 1121-1147 Request permission

Abstract:

This paper introduces new techniques for the efficient computation of Fourier transforms on symmetric groups and their homogeneous spaces. We replace the matrix multiplications in Clausen’s algorithm with sums indexed by combinatorial objects that generalize Young tableaux, and write the result in a form similar to Horner’s rule. The algorithm we obtain computes the Fourier transform of a function on $S_n$ in no more than $\frac {3}{4} n(n-1) |S_n|$ multiplications and the same number of additions. Analysis of our algorithm leads to several combinatorial problems that generalize path counting. We prove corresponding results for inverse transforms and transforms on homogeneous spaces.

References

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
P. Bürgisser, M. Clausen, A. Shokrollahi, Algebraic Complexity Theory, Springer-Verlag, Berlin, 1996.
Michael Clausen and Ulrich Baum, Fast Fourier transforms, Bibliographisches Institut, Mannheim, 1993. MR 1270670
Michael Clausen and Ulrich Baum, Fast Fourier transforms for symmetric groups: theory and implementation, Math. Comp. 61 (1993), no. 204, 833–847. MR 1192969, DOI 10.1090/S0025-5718-1993-1192969-X
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
—, Beiträge zum Entwurf schneller Spektraltransformationen, Habilitationsschrift, Fakultät für Informatik der Universität Karlsruhe (TH), 1988.
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
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
—, Group representations in probability and statistics, IMS, Hayward, CA, 1988.
Persi Diaconis and Daniel Rockmore, Efficient computation of the Fourier transform on finite groups, J. Amer. Math. Soc. 3 (1990), no. 2, 297–332. MR 1030655, DOI 10.1090/S0894-0347-1990-1030655-4
Persi Diaconis and Daniel Rockmore, Efficient computation of isotypic projections for the symmetric group, Groups and computation (New Brunswick, NJ, 1991) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11, Amer. Math. Soc., Providence, RI, 1993, pp. 87–104. MR 1235796, DOI 10.1090/dimacs/011/06
Douglas F. Elliott and K. Ramamohan Rao, Fast transforms, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, 1982. Algorithms, analyses, applications. MR 696936
Charles Hopkins, Rings with minimal condition for left ideals, Ann. of Math. (2) 40 (1939), 712–730. MR 12, DOI 10.2307/1968951
Frederick M. Goodman, Pierre de la Harpe, and Vaughan F. R. Jones, Coxeter graphs and towers of algebras, Mathematical Sciences Research Institute Publications, vol. 14, Springer-Verlag, New York, 1989. MR 999799, DOI 10.1007/978-1-4613-9641-3
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
Stephen A. Linton, Gerhard O. Michler, and Jørn B. Olsson, Fourier transforms with respect to monomial representations, Math. Ann. 297 (1993), no. 2, 253–268. MR 1241805, DOI 10.1007/BF01459500
I. G. Macdonald, Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1979. MR 553598
D. Maslen, Efficient computation of Fourier transforms on compact groups, J. Fourier Anal. Appl. (to appear).
D. Maslen and D. Rockmore Generalized FFTs - a survey of some recent results, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Groups and Computation, II, L. Finkelstein and W. Kantor (eds.), (1996), 183–237.
David K. Maslen and Daniel N. Rockmore, Separation of variables and the computation of Fourier transforms on finite groups. I, J. Amer. Math. Soc. 10 (1997), no. 1, 169–214. MR 1396896, DOI 10.1090/S0894-0347-97-00219-1
—, Separation of variables and the efficient computation of Fourier transforms on finite groups, II, (preprint).
D. Rockmore, Applications of generalized FFTs, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Groups and Computation, II, L. Finkelstein and W. Kantor (eds.), (1996).
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, DOI 10.1007/978-1-4684-9458-7
Richard P. Stanley, Differential posets, J. Amer. Math. Soc. 1 (1988), no. 4, 919–961. MR 941434, DOI 10.1090/S0894-0347-1988-0941434-9
Richard P. Stanley, Variations on differential posets, Invariant theory and tableaux (Minneapolis, MN, 1988) IMA Vol. Math. Appl., vol. 19, Springer, New York, 1990, pp. 145–165. MR 1035494
A. M. Vershik and S. V. Kerov, Locally semisimple algebras. Combinatorial theory and the $K_0$-functor, Current problems in mathematics. Newest results, Vol. 26, Itogi Nauki i Tekhniki, Akad. Nauk SSSR, Vsesoyuz. Inst. Nauchn. i Tekhn. Inform., Moscow, 1985, pp. 3–56, 260 (Russian). MR 849784