Fast Fourier transforms for the rook monoid
Martin E. Malandro, Dan Rockmore · 2012
We define the notion of the Fourier transform for the rook monoid (also called the symmetric inverse semigroup) and provide two efficient divideand-conquer algorithms (fast Fourier transforms, or FFTs) for computing it. This paper marks the first extension of group FFTs to non-group semigroups. 1