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.