  We define the notion of the Fourier transform for the rook monoid (also
called the symmetric inverse semigroup) and provide two efficient
divide-and-conquer algorithms (fast Fourier transforms, or FFTs) for computing
it. This paper marks the first extension of group FFTs to non-group semigroups.
