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
DOI: https://doi.org/10.1090/S0002-9947-09-04838-7
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?)

  • 1. U. Baum, Existence and efficient construction of fast Fourier transforms for supersolvable groups, Comput. Complex. 1/3 (1992), 235-256. MR 1165193 (93d:20031)
  • 2. L. I. Bluestein, A linear filtering approach to the computation of the discrete Fourier transform, IEEE Trans. Electroacoustics 18 (1970), no. 4, 451-455.
  • 3. M. Clausen and U. Baum, Fast Fourier transforms for symmetric groups: Theory and implementation, Math. Comput. 61 (1993), no. 204, 833-847. MR 1192969 (94a:20028)
  • 4. A. H. Clifford, Matrix representations of completely simple semigroups, Amer. J. Math. 64 (1942), no. 1, 327-342. MR 0006551 (4:4a)
  • 5. A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups, vol. 1, Mathematical Surveys No. 7, AMS, Providence, RI, 1961. MR 0132791 (24:A2627)
  • 6. -, The Algebraic Theory of Semigroups, vol. 2, Mathematical Surveys No. 7, AMS, Providence, RI, 1967. MR 0218472 (36:1558)
  • 7. J. W. Cooley and J. W. Tukey, An algorithm for machine calculation of complex Fourier series, Math. Comput. 19 (1965), 297-301. MR 0178586 (31:2843)
  • 8. C. Curtis and I. Reiner, Representation Theory of Finite Groups and Associative Algebras, John Wiley and Sons, New York, 1962. MR 0144979 (26:2519)
  • 9. P. Diaconis, A generalization of spectral analysis with application to ranked data, Ann. Statist. 17 (1989), no. 3, 949-979. MR 1015133 (91a:60025)
  • 10. P. Diaconis and D. Rockmore, Efficient computation of the Fourier transform on finite groups, J. Amer. Math. Soc. 3 (1990), no. 2, 297-332. MR 1030655 (92g:20024)
  • 11. -, Efficient computation of isotypic projections for the symmetric group, DIMACS Series in Disc. Math. and Theor. Comp. Sci. 11 (1993), 87-104. MR 1235796 (94g:20022)
  • 12. B. Farb and R. K. Dennis, Noncommutative Algebra, Graduate Texts in Mathematics, vol. 144, Springer-Verlag, New York-Heidelberg, 1993. MR 1233388 (94j:16001)
  • 13. C. Grood, A Specht module analog for the rook monoid, Electron. J. Combin. 9 (2002). MR 1887083 (2003a:05150)
  • 14. T. Halverson, Representations of the q-rook monoid, J. Algebra 273 (2004), 227-251. MR 2032458 (2005f:20011)
  • 15. R. B. Holmes, Mathematical foundation of signal processing II. The role of group theory, Massachusetts Institute of Technology Technical Report 781 (October 13, 1987).
  • 16. G. D. James, The representation theory of the symmetric groups, Lect. Notes Math., Springer-Verlag, Berlin 682 (1978). MR 513828 (80g:20019)
  • 17. S. Janson and V. Mazorchuk, Some remarks on the combinatorics of $ IS_n$, Semigroup Forum 70 (2005), no. 3, 391-405. MR 2148152 (2006c:20123)
  • 18. M. V. Lawson, Inverse Semigroups: The Theory of Partial Symmetries, World Scientific, Singapore, 1998. MR 1694900 (2000g:20123)
  • 19. M. Malandro, Fast Fourier Transforms for Inverse Semigroups, Thesis, Dartmouth College (2008).
  • 20. D. K. Maslen, The efficient computation of Fourier transforms on the symmetric group, Math. Comput. 67 (1998), no. 223, 1121-1147. MR 1468943 (99a:20009)
  • 21. D. K. Maslen and D. N. Rockmore, Adapted diameters and FFTs on groups, Proc. 6th ACM-SIAM SODA, 253-262. MR 1321855 (95k:65131)
  • 22. -, Generalized FFTs--A survey of some recent results, Proc. 1995 DIMACS Workshop on Groups and Computation 28 (1997), 183-238. MR 1444138 (98k:20020)
  • 23. -, Separation of variables and the computation of Fourier transforms on finite groups, I, J. Amer. Math. Soc. 10 (1997), no. 1, 169-214. MR 1396896 (97i:20019)
  • 24. -, The Cooley-Tukey FFT and group theory, Notices of the AMS 48 (2001), no. 10, 1151-1161. MR 1861656 (2002k:20022)
  • 25. W. D. Munn, On semigroup algebras, Proc. Cambridge Philos. Soc. 51 (1955), 1-15. MR 0066355 (16:561c)
  • 26. -, The characters of the symmetric inverse semigroup, Proc. Cambridge Philos. Soc. 53 (1957), 13-18. MR 0081910 (18:465d)
  • 27. -, Matrix representations of semigroups, Proc. Cambridge Philos. Soc. 53 (1957), 5-12. MR 0082050 (18:489g)
  • 28. J. Rhodes and Y. Zalcstein, Elementary representation and character theory of finite semigroups and its application, Monoids and Semigroups with Applications, pp. 334-367, World Sci. Publishing, River Edge, NJ, 1991. MR 1142387 (92k:20129)
  • 29. D. N. Rockmore, Recent progress and applications in group FFTs, NATO Science Series, Computational Noncommutative Algebra and Applications, vol. 136, pp. 227-254, Kluwer Acad. Publ., Dordrecht, 2004. MR 2159215 (2007j:43012)
  • 30. J. P. Serre, Linear Representations of Finite Groups, Graduate Texts in Mathematics, vol. 42, Springer-Verlag, New York-Heidelberg, 1977. MR 0450380 (56:8675)
  • 31. L. Solomon, Representations of the rook monoid, J. Algebra 256 (2002), 309-342. MR 1939108 (2003m:20091)
  • 32. R. Stanley, Enumerative Combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, 1997. MR 1442260 (98a:05001)
  • 33. B. Steinberg, Mobius functions and semigroup representation theory, J. Comb. Theor. Ser. A. 113 (2006), 866-881. MR 2231092 (2007c:20144)
  • 34. -, Möbius functions and semigroup representation theory II: Character formulas and multiplicities, Adv. In Math. 217 (2008), 1521-1557. MR 2382734
  • 35. F. Yates, The design and analysis of factorial experiments, Imp. Bur. Soil Sci. Tech. Comm. 35 (1937).

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.

American Mathematical Society