Fast Fourier transforms for finite inverse semigroups

DOI10.1016/J.JALGEBRA.2009.11.031zbMATH Open1197.65235arXiv0905.1340OpenAlexW2077807450MaRDI QIDQ986071FDOQ986071

Authors: Martin E. Malandro 

Publication date: 11 August 2010

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Title not available (Why is that?)
• Title not available (Why is that?)
• Representations of the rook monoid.
• Title not available (Why is that?)
• On the structure of semigroups
• Title not available (Why is that?)
• Title not available (Why is that?)
• A generalization of spectral analysis with application to ranked data
• Some remarks on the combinatorics of \(\mathcal{IS}_n\).
• The efficient computation of Fourier transforms on the symmetric group
• Efficient Computation of the Fourier Transform on Finite Groups
• Möbius functions and semigroup representation theory. II: Character formulas and multiplicities.
• Separation of variables and the computation of Fourier transforms on finite groups, I
• Fast Fourier transforms for wreath products
• The Cooley-Tukey FFT and group theory.
• Fast Fourier Transforms for Symmetric Groups: Theory and Implementation
• Title not available (Why is that?)
• Fast Fourier transforms for the rook monoid.
• Recent progress and applications in group FFTs

Cited In (15)

• Fast Fourier transforms for wreath products
• Fast Fourier transforms for the rook monoid.
• Factoring the Dedekind-Frobenius determinant of a semigroup
• Computing Fourier transforms and convolutions of \(S_{n - 1}\)-invariant signals on \(S_n\) in time linear in \(n\)
• Fast zeta transforms for lattices with few irreducibles
• The efficient computation of Fourier transforms on semisimple algebras
• Non-commutative Stone duality
• Simplicity of augmentation submodules for transformation monoids
• Varieties of Boolean inverse semigroups
• 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)