Fast Fourier Transforms for Finite Inverse Semigroups
arXiv:0905.1340 · doi:10.1016/j.jalgebra.2009.11.031
Abstract
We extend the theory of fast Fourier transforms on finite groups to finite inverse semigroups. We use a general method for constructing the irreducible representations of a finite inverse semigroup to reduce the problem of computing its Fourier transform to the problems of computing Fourier transforms on its maximal subgroups and a fast zeta transform on its poset structure. We then exhibit explicit fast algorithms for particular inverse semigroups of interest--specifically, for the rook monoid and its wreath products by arbitrary finite groups.
ver 3: Added improved upper and lower bounds for the memory required by the fast zeta transform on the rook monoid. ver 2: Corrected typos and (naive) bounds on memory requirements. 30 pages, 0 figures