Fast Fourier transforms for finite inverse semigroups

DOI10.1016/J.JALGEBRA.2009.11.031MaRDI QIDQ986071zbMATH OpenOpenAlexFDO

Authors Martin E. Malandro

Publication date 11 August 2010

Published in Journal of Algebra (Search for Journal in Brave)

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

zbMATH Keywords

fast Fourier transformmaximal subgroupsrepresentation theoryrook monoidfinite inverse semigroupzeta transform

Mathematics Subject Classification ID

Fourier and Fourier-Stieltjes transforms on nonabelian groups and on semigroups, etc. (43A30) Numerical methods for discrete and fast Fourier transforms (65T50) Inverse semigroups (20M18)

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

Recommendations

• Fast Fourier transforms for the rook monoid.
• Fourier inversion for finite inverse semigroups
• Efficient computation of Fourier inversion for finite groups
• Efficient Computation of the Fourier Transform on Finite Groups
• scientific article; zbMATH DE number 475354

Cites work

• 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 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?)
• A generalization of spectral analysis with application to ranked data
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Efficient Computation of the Fourier Transform on Finite Groups
• Fast Fourier Transforms for Symmetric Groups: Theory and Implementation
• Fast Fourier transforms for the rook monoid.
• Fast Fourier transforms for wreath products
• Möbius functions and semigroup representation theory. II: Character formulas and multiplicities.
• On the structure of semigroups
• Recent progress and applications in group FFTs
• 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

Cited in

(15)

• Fast Fourier transforms for wreath products
• Factoring the Dedekind-Frobenius determinant of a semigroup
• Fast Fourier transforms for the rook monoid.
• Computing Fourier transforms and convolutions of \(S_{n - 1}\)-invariant signals on \(S_n\) in time linear in \(n\)
• The efficient computation of Fourier transforms on semisimple algebras
• Fast zeta transforms for lattices with few irreducibles
• Varieties of Boolean inverse semigroups
• Simplicity of augmentation submodules for transformation monoids
• Non-commutative Stone duality
• Fourier inversion for finite inverse semigroups
• Inverse semigroup spectral analysis for partially ranked data
• Character theory of monoids over an arbitrary field.
• Fast Möbius inversion in semimodular lattices and ER-labelable posets
• Quivers of monoids with basic algebras.
• Recent developments in inverse semigroup theory

This page was built for publication: Fast Fourier transforms for finite inverse semigroups

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