Fast Fourier transforms for finite inverse semigroups (Q986071): Difference between revisions

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 \({\mathcal O}(|S|\, (\log |S|)^c)\) operations.