Fast Fourier transforms for symmetric groups: theory and implementation

Clausen, Michael; Baum, Ulrich

doi:10.1090/S0025-5718-1993-1192969-X

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

A linear filtering approach to the computation of the discrete Fourier transform

AU-18

Beiträge zum Entwurf schneller Spektraltransformationen

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

Symmetry adaptation to sequences of finite groups

Fast Fourier transforms on symmetric groups

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