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
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?)


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