Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 

 

Fast Fourier transforms for the rook monoid


Authors: Martin Malandro and Dan Rockmore
Journal: Trans. Amer. Math. Soc. 362 (2010), 1009-1045
MSC (2000): Primary 20C40, 20M18, 43A30; Secondary 20M30, 68W40
Published electronically: September 17, 2009
MathSciNet review: 2551514
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We define the notion of the Fourier transform for the rook monoid (also called the symmetric inverse semigroup) and provide two efficient divide-and-conquer algorithms (fast Fourier transforms, or FFTs) for computing it. This paper marks the first extension of group FFTs to nongroup semigroups.


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


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 20C40, 20M18, 43A30, 20M30, 68W40

Retrieve articles in all journals with MSC (2000): 20C40, 20M18, 43A30, 20M30, 68W40


Additional Information

Martin Malandro
Affiliation: Department of Mathematics, 6188 Kemeny Hall, Dartmouth College, Hanover, New Hampshire 03755
Address at time of publication: Department of Mathematics and Statistics, Sam Houston State University, Box 2206, Huntsville, Texas 77341-2206
Email: malandro@shsu.edu

Dan Rockmore
Affiliation: Department of Mathematics, 6188 Kemeny Hall, Dartmouth College, Hanover, New Hampshire 03755
Email: rockmore@cs.dartmouth.edu

DOI: https://doi.org/10.1090/S0002-9947-09-04838-7
Keywords: Rook monoid, fast Fourier transform, FFT, inverse semigroup, partially ranked data
Received by editor(s): September 25, 2007
Received by editor(s) in revised form: June 2, 2008
Published electronically: September 17, 2009
Additional Notes: The first author was supported by a graduate fellowship.
The second author was supported by AFOSR under grant FA9550-06-1-0027.
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.