{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:36:50Z","timestamp":1787323010834,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>This paper continues the study of Fourier transforms on finite inverse semigroups, with a focus on Fourier inversion theorems and FFTs for new classes of inverse semigroups. We begin by introducing four inverse semigroup generalizations of the Fourier inversion theorem for finite groups. Next, we describe a general approach to the construction of fast inverse Fourier transforms for finite inverse semigroups complementary to an approach to FFTs given in previous work. Finally, we give fast inverse Fourier transforms for the symmetric inverse monoid and its wreath product by arbitrary finite groups, as well as fast Fourier and inverse Fourier transforms for the planar rook monoid, the partial cyclic shift monoid, and the partial rotation monoid.<\/jats:p>","DOI":"10.1137\/130932028","type":"journal-article","created":{"date-parts":[[2015,2,5]],"date-time":"2015-02-05T12:47:56Z","timestamp":1423140476000},"page":"269-296","source":"Crossref","is-referenced-by-count":0,"title":["Fourier Inversion for Finite Inverse Semigroups"],"prefix":"10.1137","volume":"29","author":[{"given":"Martin E.","family":"Malandro","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,2,5]]},"reference":[{"key":"atypb1","unstructured":"N. Ailon,\n                      An $n\\log n$ Lower Bound for Fourier Transform Computation in the Well Conditioned Model\n                      , preprint, arXiv:1403.1307, 2014."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200062"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/0220028"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"A. Bjo\u0308rklund, T. Husfeldt, P. Kaski, and M. Koivisto,\n                      Fourier meets Mo\u0308bius: Fast subset convolution\n                      , in Proceedings of the 39th ACM Symposium on Theory of Computing, STOC '07, 2007, pp. 67-74.","DOI":"10.1145\/1250790.1250801"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"A. Bjo\u0308rklund, T. Husfeldt, P. Kaski, M. Koivisto, J. Nederlof, and P. Parviainen,\n                      Fast zeta transforms for lattices with few irreducibles\n                      , in Proceedings of the 23rd ACM-SIAM SODA, 2012, pp. 1436-1444.","DOI":"10.1137\/1.9781611973099.113"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1109\/TAU.1970.1162132"},{"key":"atypb7","unstructured":"E. O. Brigham,\n                      The Fast Fourier Transform and Its Applications\n                      , Prentice-Hall, Englewood Cliffs, NJ, 1988."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1993-1192969-X"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"A. H. Clifford and G. B. Preston,\n                      The Algebraic Theory of Semigroups, Vol.\n                      1, Math. Surveys Manogr. 7, AMS, Providence, RI, 1961.","DOI":"10.1090\/surv\/007.1\/01"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"P. Diaconis,\n                      Group Representations in Probability and Statistics,\n                      IMS Lecture Notes Monogr. Ser. 11, Institute of Mathematical Statistics, Hayward, CA, 1988.","DOI":"10.1214\/lnms\/1215467407"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176347251"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.4171\/LEM\/55-1-3"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.2307\/1969317"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"M. V. Lawson,\n                      Inverse Semigroups: The Theory of Partial Symmetries\n                      , World Scientific, Singapore, 1998.","DOI":"10.1142\/3645"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-09-04838-7"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2009.11.031"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2012.07.009"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-98-00964-8"},{"key":"atypb20","unstructured":"D. K. Maslen and D. N. Rockmore,\n                      Adapted diameters and FFTs on groups\n                      , in Proceedings of the 6th ACM-SIAM SODA, 1995, pp. 253-262."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100029868"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100031947"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100031935"},{"key":"atypb24","unstructured":"W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery,\n                      Numerical Recipes: The Art of Scientific Computing\n                      , 3rd ed., Cambridge University Press, Cambridge, UK, 2007."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1006\/acha.1995.1020"},{"key":"atypb26","first-page":"329","author":"Rockmore D. N.","year":"1997","journal-title":"Proceedings of DIMACS Workshop in Groups and Computation"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"J. P. Serre,\n                      Linear Representations of Finite Groups,\n                      Grad. Texts in Math. 42, Springer-Verlag, New York, 1977.","DOI":"10.1007\/978-1-4684-9458-7"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-8693(02)00004-2"},{"key":"atypb29","unstructured":"R. Stanley,\n                      Enumerative Combinatorics, Vol.\n                      1, Cambridge Stud. Adv. Math. 49, Cambridge University Press, Cambridge, UK, 1997."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2007.12.001"},{"key":"atypb31","unstructured":"F. Yates,\n                      The Design and Analysis of Factorial Experiments\n                      , Imperial Bureau of Soil Science, 1937."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130932028","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:36:57Z","timestamp":1787319417000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130932028"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130932028"],"URL":"https:\/\/doi.org\/10.1137\/130932028","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}