05768599

j

05768599 Malandro, Martin E. Fast Fourier transforms for finite inverse semigroups. J. Algebra 324, No. 2, 282-312 (2010). 2010 Elsevier Science (Academic Press), San Diego, CA EN fast Fourier transform finite inverse semigroup rook monoid representation theory maximal subgroups zeta transform

doi:10.1016/j.jalgebra.2009.11.031

The fast Fourier transform (FFT) on a finite group is extended to the FFT on a finite inverse semigroup. The most important finite inverse semigroup is the rook monoid. The author creates a general framework for constructing FFTs on finite inverse semigroups. The problem of computing the Fourier transform on a finite inverse semigroup is reduced to the problems of computing Fourier transforms on its maximal subgroups and a fast zeta transform on its poset structure. Further the author constructs FFTs for specific finite inverse semigroups $S$ (such as the rook monoid and the wreath product of the rook monoid with a finite group) which require ${\cal O}(|S|\, (\log |S|)^c)$ operations. Manfred Tasche (Rostock)