The efficient computation of Fourier transforms on the symmetric group
Author:
David K. Maslen
Journal:
Math. Comp. 67 (1998), 1121-1147
MSC (1991):
Primary 20C30, 20C40; Secondary 65T20, 05E10
DOI:
https://doi.org/10.1090/S0025-5718-98-00964-8
MathSciNet review:
1468943
Full-text PDF
Abstract | References | Similar Articles | Additional Information
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 in no more than
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.
- 1. T. Beth, Verfahren der schnellen Fourier-Transformation, Teubner Studienbücher, Stuttgart, 1984. MR 86g:65002
- 2. P. Bürgisser, M. Clausen, A. Shokrollahi, Algebraic Complexity Theory, Springer-Verlag, Berlin, 1996. CMP 97:10
- 3. M. Clausen and U. Baum, Fast Fourier transforms, Wissenschaftsverlag, Mannheim, 1993. MR 96i:68001
- 4. -, Fast Fourier transforms for symmetric groups, theory and implementation, Math. Comp. 61(204) (1993), 833-847. MR 94a:20028
- 5. M. Clausen, Fast generalized Fourier transforms, Theoret. Comput. Sci. 67 (1989), 55-63. MR 91f:68081
- 6. -, Beiträge zum Entwurf schneller Spektraltransformationen, Habilitationsschrift, Fakultät für Informatik der Universität Karlsruhe (TH), 1988.
- 7. J. W. Cooley and J. W. Tukey, An algorithm for machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297-301. MR 31:2843
- 8. P. Diaconis, A generalization of spectral analysis with applications to ranked data, Ann. Stat. 17 (1989), 949-979. MR 91a:60025
- 9. -, Group representations in probability and statistics, IMS, Hayward, CA, 1988.
- 10. P. Diaconis and D. Rockmore, Efficient computation of the Fourier transform on finite groups, J. Amer. Math. Soc. 3(2) (1990), 297-332. MR 92g:20024
- 11. -, Efficient computation of isotypic projections for the symmetric group, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 11, L. Finkelstein and W. Kantor (eds.), 1993, 87-104. MR 94g:20022
- 12. D. Elliott and K. Rao, Fast transforms: algorithms, analyses, and applications, Academic, New York, 1982. MR 85e:94001
- 13.
I. Gel
fand and M. Tsetlin, Finite dimensional representations of the group of unimodular matrices, Dokl. Akad. Nauk SSSR 71 (1950), 825-828 (Russian). MR 12:9j
- 14. F. Goodman, P. de la Harpe, and V. Jones, Coxeter graphs and towers of algebras, Springer-Verlag, New York, 1989. MR 91c:46082
- 15. G. James and A. Kerber, The representation theory of the symmetric group, Encyclopedia of Mathematics and its Applications, vol. 16, Addison-Wesley, Reading MA, 1981. MR 83k:20003
- 16. S. Linton, G. Michler, and J. Olsson, Fourier transforms with respect to monomial representations, Math. Ann. 297 (1993), 253-268. MR 94i:20015
- 17. I. Macdonald, Symmetric functions and Hall polynomials, Oxford University Press, 1979. MR 84g:05003
- 18. D. Maslen, Efficient computation of Fourier transforms on compact groups, J. Fourier Anal. Appl. (to appear).
- 19. 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. CMP 97:11
- 20. -, Separation of variables and the efficient computation of Fourier transforms on finite groups, I, J. Amer. Math. Soc. 10 (1) (1997). MR 97i:20019
- 21. -, Separation of variables and the efficient computation of Fourier transforms on finite groups, II, (preprint).
- 22. D. Rockmore, Applications of generalized FFTs, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Groups and Computation, II, L. Finkelstein and W. Kantor (eds.), (1996). CMP 97:11
- 23. J. Serre, Linear representations of finite groups, Springer-Verlag, New York, 1977. MR 56:8675
- 24. R. Stanley, Differential Posets, J. Amer. Math. Soc. 1(4) (1988), 919-961. MR 89h:06005
- 25. R. Stanley, Variations on differential posets, in Invariant Theory and Tableaux (ed. D. Stanton), IMA Vol. Math. Appl., Springer, New York, 1990, 145-165. MR 91h:06004
- 26.
A. Vershik and S. Kerov, Locally semisimple algebras. Combinatorial theory and the
functor, Itogi Nauki i Tekhniki, Sovremennye Problemy Matematiki, Noveishie Dostizheniya, Vol. 26 (1985), 3-56. MR 88h:22009
Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 20C30, 20C40, 65T20, 05E10
Retrieve articles in all journals with MSC (1991): 20C30, 20C40, 65T20, 05E10
Additional Information
David K. Maslen
Affiliation:
Institut des Haute Études Scientifiques, Le Bois-Marie, 35 Route de Chartres, 91440, Bures-sur-Yvette, France
Address at time of publication:
Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098SJ, Amsterdam, The Netherlands
Email:
maslen@cwi.nl
DOI:
https://doi.org/10.1090/S0025-5718-98-00964-8
Received by editor(s):
August 21, 1996
Received by editor(s) in revised form:
April 23, 1997
Additional Notes:
An extended abstract summarizing these results appears in the FPSAC ’97 proceedings volume.
Article copyright:
© Copyright 1998
American Mathematical Society