Fast Fourier transforms for symmetric groups: theory and implementation
HTML articles powered by AMS MathViewer
- by Michael Clausen and Ulrich Baum PDF
- Math. Comp. 61 (1993), 833-847 Request permission
Abstract:
Recently, it has been proved that a Fourier transform for the symmetric group ${S_n}$ based on Young’s seminormal form can be evaluated in less than $0.5({n^3} + {n^2})n!$ arithmetic operations. We look at this algorithm in more detail and show that it allows an efficient software implementation using appropriate data structures. We also describe a similarly efficient algorithm for the inverse Fourier transform. We compare the time and memory requirements of our program to those of other existing implementations.References
- Ulrich Baum, Existence and efficient construction of fast Fourier transforms on supersolvable groups, Comput. Complexity 1 (1991), no. 3, 235–256. MR 1165193, DOI 10.1007/BF01200062
- Ulrich Baum and Michael Clausen, Some lower and upper complexity bounds for generalized Fourier transforms and their inverses, SIAM J. Comput. 20 (1991), no. 3, 451–459. MR 1094524, DOI 10.1137/0220028 L. I. Bluestein, A linear filtering approach to the computation of the discrete Fourier transform, IEEE Trans. AU-18 (1970), 451-455. M. Clausen, Beiträge zum Entwurf schneller Spektraltransformationen, Habilitationsschrift, Universität Karlsruhe, 1988.
- 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
- 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
- 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 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
- N. F. J. Inglis, R. W. Richardson, and J. Saxl, An explicit model for the complex representations of $S_n$, Arch. Math. (Basel) 54 (1990), no. 3, 258–259. MR 1037615, DOI 10.1007/BF01188521
- 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 D. J. Klein, C. H. Carlisle, and F. A. Matsen, Symmetry adaptation to sequences of finite groups, Adv. Quantum Chemistry, vol. 5, Academic Press, New York, 1970, pp. 219-260. S. A. Linton, G. O. Michler, and J. B. Olsson, Fast Fourier transforms on symmetric groups, preprint, Universität Essen, 1991.
- Kazuo Murota and Kiyohiro Ikeda, Computational use of group theory in bifurcation analysis of symmetric structures, SIAM J. Sci. Statist. Comput. 12 (1991), no. 2, 273–297. MR 1087761, DOI 10.1137/0912016
- 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
- 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
- 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
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Math. Comp. 61 (1993), 833-847
- MSC: Primary 20C40; Secondary 20C30, 68Q40
- DOI: https://doi.org/10.1090/S0025-5718-1993-1192969-X
- MathSciNet review: 1192969