Fast Fourier transforms for the rook monoid

Malandro, Martin; Rockmore, Dan

doi:10.1090/S0002-9947-09-04838-7

Fast Fourier transforms for the rook monoid
HTML articles powered by AMS MathViewer

by Martin Malandro and Dan Rockmore PDF

Trans. Amer. Math. Soc. 362 (2010), 1009-1045 Request permission

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

Ulrich Baum, Existence and efficient construction of fast Fourier transforms on supersolvable groups, Comput. Complexity 1 (1991), no. 3, 235–256. MR 1165193, DOI 10.1007/BF01200062
L. I. Bluestein, A linear filtering approach to the computation of the discrete Fourier transform, IEEE Trans. Electroacoustics 18 (1970), no. 4, 451–455.
Michael Clausen and Ulrich Baum, Fast Fourier transforms for symmetric groups: theory and implementation, Math. Comp. 61 (1993), no. 204, 833–847. MR 1192969, DOI 10.1090/S0025-5718-1993-1192969-X
A. H. Clifford, Matrix representations of completely simple semigroups, Amer. J. Math. 64 (1942), 327–342. MR 6551, DOI 10.2307/2371687
A. H. Clifford and G. B. Preston, The algebraic theory of semigroups. Vol. I, Mathematical Surveys, No. 7, American Mathematical Society, Providence, R.I., 1961. MR 0132791
A. H. Clifford and G. B. Preston, The algebraic theory of semigroups. Vol. II, Mathematical Surveys, No. 7, American Mathematical Society, Providence, R.I., 1967. MR 0218472
James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297–301. MR 178586, DOI 10.1090/S0025-5718-1965-0178586-1
Charles W. Curtis and Irving Reiner, Representation theory of finite groups and associative algebras, Pure and Applied Mathematics, Vol. XI, Interscience Publishers (a division of John Wiley & Sons, Inc.), New York-London, 1962. MR 0144979
Persi Diaconis, A generalization of spectral analysis with application to ranked data, Ann. Statist. 17 (1989), no. 3, 949–979. MR 1015133, DOI 10.1214/aos/1176347251
Persi Diaconis and Daniel Rockmore, Efficient computation of the Fourier transform on finite groups, J. Amer. Math. Soc. 3 (1990), no. 2, 297–332. MR 1030655, DOI 10.1090/S0894-0347-1990-1030655-4
Persi Diaconis and Daniel Rockmore, Efficient computation of isotypic projections for the symmetric group, Groups and computation (New Brunswick, NJ, 1991) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11, Amer. Math. Soc., Providence, RI, 1993, pp. 87–104. MR 1235796, DOI 10.1090/dimacs/011/06
Benson Farb and R. Keith Dennis, Noncommutative algebra, Graduate Texts in Mathematics, vol. 144, Springer-Verlag, New York, 1993. MR 1233388, DOI 10.1007/978-1-4612-0889-1
Cheryl Grood, A Specht module analog for the rook monoid, Electron. J. Combin. 9 (2002), no. 1, Research Paper 2, 10. MR 1887083
Tom Halverson, Representations of the $q$-rook monoid, J. Algebra 273 (2004), no. 1, 227–251. MR 2032458, DOI 10.1016/j.jalgebra.2003.11.002
R. B. Holmes, Mathematical foundation of signal processing II. The role of group theory, Massachusetts Institute of Technology Technical Report 781 (October 13, 1987).
G. D. James, The representation theory of the symmetric groups, Lecture Notes in Mathematics, vol. 682, Springer, Berlin, 1978. MR 513828
Svante Janson and Volodymyr Mazorchuk, Some remarks on the combinatorics of ${\scr {IS}}_n$, Semigroup Forum 70 (2005), no. 3, 391–405. MR 2148152, DOI 10.1007/s00233-004-0158-5
Mark V. Lawson, Inverse semigroups, World Scientific Publishing Co., Inc., River Edge, NJ, 1998. The theory of partial symmetries. MR 1694900, DOI 10.1142/9789812816689
M. Malandro, Fast Fourier Transforms for Inverse Semigroups, Thesis, Dartmouth College (2008).
David K. Maslen, The efficient computation of Fourier transforms on the symmetric group, Math. Comp. 67 (1998), no. 223, 1121–1147. MR 1468943, DOI 10.1090/S0025-5718-98-00964-8
David K. Maslen and Daniel N. Rockmore, Adapted diameters and the efficient computation of Fourier transforms on finite groups, Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1995) ACM, New York, 1995, pp. 253–262. MR 1321855
David K. Maslen and Daniel N. Rockmore, Generalized FFTs—a survey of some recent results, Groups and computation, II (New Brunswick, NJ, 1995) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 28, Amer. Math. Soc., Providence, RI, 1997, pp. 183–237. MR 1444138, DOI 10.1090/s0894-0347-97-00219-1
David K. Maslen and Daniel N. Rockmore, 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, DOI 10.1090/S0894-0347-97-00219-1
David K. Maslen and Daniel N. Rockmore, The Cooley-Tukey FFT and group theory, Notices Amer. Math. Soc. 48 (2001), no. 10, 1151–1160. MR 1861656
W. D. Munn, On semigroup algebras, Proc. Cambridge Philos. Soc. 51 (1955), 1–15. MR 66355, DOI 10.1017/s0305004100029868
W. D. Munn, The characters of the symmetric inverse semigroup, Proc. Cambridge Philos. Soc. 53 (1957), 13–18. MR 81910, DOI 10.1017/s0305004100031947
W. D. Munn, Matrix representations of semigroups, Proc. Cambridge Philos. Soc. 53 (1957), 5–12. MR 82050, DOI 10.1017/s0305004100031935
John Rhodes and Yechezkel Zalcstein, Elementary representation and character theory of finite semigroups and its application, Monoids and semigroups with applications (Berkeley, CA, 1989) World Sci. Publ., River Edge, NJ, 1991, pp. 334–367. MR 1142387
Daniel N. Rockmore, Recent progress and applications in group FFTs, Computational noncommutative algebra and applications, NATO Sci. Ser. II Math. Phys. Chem., vol. 136, Kluwer Acad. Publ., Dordrecht, 2004, pp. 227–254. MR 2159215, DOI 10.1007/1-4020-2307-3_{9}
Jean-Pierre Serre, Linear representations of finite groups, Graduate Texts in Mathematics, Vol. 42, Springer-Verlag, New York-Heidelberg, 1977. Translated from the second French edition by Leonard L. Scott. MR 0450380
Louis Solomon, Representations of the rook monoid, J. Algebra 256 (2002), no. 2, 309–342. MR 1939108, DOI 10.1016/S0021-8693(02)00004-2
Richard P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota; Corrected reprint of the 1986 original. MR 1442260, DOI 10.1017/CBO9780511805967
Benjamin Steinberg, Möbius functions and semigroup representation theory, J. Combin. Theory Ser. A 113 (2006), no. 5, 866–881. MR 2231092, DOI 10.1016/j.jcta.2005.08.004
Benjamin Steinberg, Möbius functions and semigroup representation theory. II. Character formulas and multiplicities, Adv. Math. 217 (2008), no. 4, 1521–1557. MR 2382734, DOI 10.1016/j.aim.2007.12.001
F. Yates, The design and analysis of factorial experiments, Imp. Bur. Soil Sci. Tech. Comm. 35 (1937).