Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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

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: http://dx.doi.org/10.1090/S0002-9947-09-04838-7
PII: S 0002-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.