Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

The efficient computation of Fourier transforms on the symmetric group


Author: David K. Maslen
Journal: Math. Comp. 67 (1998), 1121-1147
MSC (1991): Primary 20C30, 20C40; Secondary 65T20, 05E10
MathSciNet review: 1468943
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper introduces new techniques for the efficient computation of Fourier transforms on symmetric groups and their homogeneous spaces. We replace the matrix multiplications in Clausen's algorithm with sums indexed by combinatorial objects that generalize Young tableaux, and write the result in a form similar to Horner's rule. The algorithm we obtain computes the Fourier transform of a function on $S_n$ in no more than $\frac{3}{4} n(n-1) \left| S_n \right|$ multiplications and the same number of additions. Analysis of our algorithm leads to several combinatorial problems that generalize path counting. We prove corresponding results for inverse transforms and transforms on homogeneous spaces.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 20C30, 20C40, 65T20, 05E10

Retrieve articles in all journals with MSC (1991): 20C30, 20C40, 65T20, 05E10


Additional Information

David K. Maslen
Affiliation: Institut des Haute Études Scientifiques, Le Bois-Marie, 35 Route de Chartres, 91440, Bures-sur-Yvette, France
Address at time of publication: Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098SJ, Amsterdam, The Netherlands
Email: maslen@cwi.nl

DOI: http://dx.doi.org/10.1090/S0025-5718-98-00964-8
PII: S 0025-5718(98)00964-8
Received by editor(s): August 21, 1996
Received by editor(s) in revised form: April 23, 1997
Additional Notes: An extended abstract summarizing these results appears in the FPSAC ’97 proceedings volume.
Article copyright: © Copyright 1998 American Mathematical Society