Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Fast Fourier transforms for symmetric groups: theory and implementation


Authors: Michael Clausen and Ulrich Baum
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] U. Baum, Existence and efficient construction of fast Fourier transforms on supersolvable groups, Comput. Complex. 1/3 (1992), 235-256. MR 1165193 (93d:20031)
  • [2] U. Baum and M. Clausen, Some lower and upper complexity bounds for generalized Fourier transforms and their inverses, SIAM J. Comput. 2 (1991), 451-459. MR 1094524 (91m:68100)
  • [3] L. I. Bluestein, A linear filtering approach to the computation of the discrete Fourier transform, IEEE Trans. AU-18 (1970), 451-455.
  • [4] M. Clausen, Beiträge zum Entwurf schneller Spektraltransformationen, Habilitationsschrift, Universität Karlsruhe, 1988.
  • [5] -, Fast generalized Fourier transforms, Theoret. Comput. Sci. 67 (1989), 55-63. MR 1015084 (91f:68081)
  • [6] J. W. Cooley and J. W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297-301. MR 0178586 (31:2843)
  • [7] P. Diaconis, A generalization of spectral analysis with application to ranked data, Ann. Statist. 17 (1989), 949-979. MR 1015133 (91a:60025)
  • [8] -, Group representations in probability and statistics, IMS Lecture Notes--Monograph Ser., vol. 11, Inst. Math. Statist., Hayward, CA, 1988. MR 964069 (90a:60001)
  • [9] P. Diaconis and D. Rockmore, Efficient computation of the Fourier transform on finite groups, J. Amer. Math. Soc. 3 (1990), 297-332. MR 1030655 (92g:20024)
  • [10] 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), 258-259. MR 1037615 (91d:20017)
  • [11] G. D. James and A. Kerber, The representation theory of the symmetric group, Addison-Wesley, Reading, MA, 1981. MR 644144 (83k:20003)
  • [12] 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.
  • [13] S. A. Linton, G. O. Michler, and J. B. Olsson, Fast Fourier transforms on symmetric groups, preprint, Universität Essen, 1991.
  • [14] K. Murota and K. Ikeda, Computational use of group theory in bifurcation analysis of symmetric structures, SIAM J. Sci. Statist. Comput. 12 (1991), 273-297. MR 1087761 (92a:65174)
  • [15] D. Rockmore, Computation of Fourier transforms on the symmetric group, Computers and Mathematics (E. Kaltofen and S. M. Watt, eds.), Springer, Berlin and New York, 1989, pp. 156-165. MR 1005972 (90i:20013)
  • [16] J. P. Serre, Linear representations of finite groups, Springer, Berlin and New York, 1977. MR 0450380 (56:8675)
  • [17] S. Winograd, On computing the discrete Fourier transform, Math. Comp. 32 (1978), 175-199. MR 0468306 (57:8142)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 20C40, 20C30, 68Q40

Retrieve articles in all journals with MSC: 20C40, 20C30, 68Q40


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1993-1192969-X
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society