Fast Fourier transforms for the rook monoid.

DOI10.1090/S0002-9947-09-04838-7MaRDI QIDQ5189159zbMATH OpenFDO

Authors Martin E. Malandro, Daniel N. Rockmore

Publication date 8 March 2010

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0709.4175

zbMATH Keywords

divide-and-conquer algorithmsfast Fourier transformsFFTsinverse semigroupspartially ranked datarook monoids

Mathematics Subject Classification ID

Inverse semigroups (20M18) Representation of semigroups; actions of semigroups on sets (20M30) Fourier and Fourier-Stieltjes transforms on nonabelian groups and on semigroups, etc. (43A30) Numerical methods for discrete and fast Fourier transforms (65T50) Analysis of algorithms (68W40)

Abstract: 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.

Recommendations

• Fast Fourier transforms for finite inverse semigroups
• The Fast Fourier Transform
• Fourier inversion for finite inverse semigroups
• Fast Fourier Transforms for Symmetric Groups: Theory and Implementation
• Efficient computation of Fourier inversion for finite groups

Cites work

• A generalization of spectral analysis with application to ranked data
• A Specht module analog for the rook monoid
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Efficient Computation of the Fourier Transform on Finite Groups
• Existence and efficient construction of fast Fourier transforms on supersolvable groups
• Fast Fourier transforms for finite inverse semigroups
• Fast Fourier Transforms for Symmetric Groups: Theory and Implementation
• scientific article; zbMATH DE number 3125734 (Why is no real title available?)
• scientific article; zbMATH DE number 3125735 (Why is no real title available?)
• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• scientific article; zbMATH DE number 3552764 (Why is no real title available?)
• scientific article; zbMATH DE number 459354 (Why is no real title available?)
• scientific article; zbMATH DE number 464655 (Why is no real title available?)
• scientific article; zbMATH DE number 475357 (Why is no real title available?)
• scientific article; zbMATH DE number 1004938 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 1761434 (Why is no real title available?)
• scientific article; zbMATH DE number 910881 (Why is no real title available?)
• scientific article; zbMATH DE number 3212917 (Why is no real title available?)
• scientific article; zbMATH DE number 3284302 (Why is no real title available?)
• scientific article; zbMATH DE number 3108421 (Why is no real title available?)
• Matrix Representations of Completely Simple Semigroups
• Möbius functions and semigroup representation theory.
• Möbius functions and semigroup representation theory. II: Character formulas and multiplicities.
• Recent progress and applications in group FFTs
• Representations of the \(q\)-rook monoid.
• Representations of the rook monoid.
• Separation of variables and the computation of Fourier transforms on finite groups, I
• Some remarks on the combinatorics of \(\mathcal{IS}_n\).
• The Cooley-Tukey FFT and group theory.
• The efficient computation of Fourier transforms on the symmetric group
• The representation theory of the symmetric groups

Cited in

(8)

• The efficient computation of Fourier transforms on semisimple algebras
• Simplicity of augmentation submodules for transformation monoids
• Inverse semigroup spectral analysis for partially ranked data
• Character theory of monoids over an arbitrary field.
• Quivers of monoids with basic algebras.
• Fourier inversion for finite inverse semigroups
• Fast zeta transforms for lattices with few irreducibles
• Fast Fourier transforms for finite inverse semigroups

This page was built for publication: Fast Fourier transforms for the rook monoid.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5189159)