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

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

Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society