Double coset decompositions and computational harmonic analysis on groups
From MaRDI portal
The paper describes a new technique for the efficient computation of a Fourier transform on a finite group. It utilizes the decomposition of a group into double cosets to derive algorithms that generalize the Cooley-Tukey FFT to arbitrary finite groups. The result is applied to the special linear group: Let \(q\) be an odd prime power. The Fourier transform of a complex valued function can be computed in no more than \(({1\over 2}q+3+16\log q)\cdot (q^3-q)\) scalar operations if a system of Gel'fand-Tsetlin bases for the irreducible representations of \(SL_2(F_q)\) are used.
Recommendations
- Publication:4886055
- The efficient computation of Fourier transforms on the symmetric group
- Efficient computation of Fourier transforms on compact groups
- Linear time Fourier transforms of \(S_{n-k}\)-invariant functions on the symmetric group \(S_n\)
- Separation of variables and the computation of Fourier transforms on finite groups, I
Cites work
- A generalization of spectral analysis with application to ranked data
- Algebraic complexity theory. I: An introduction
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Average running time of the fast Fourier transform
- Complex Representations of 𝐺𝐿(2,𝐾) for Finite Fields 𝐾
- Computing Irreducible Representations of Finite Groups
- Computing Irreducible Representations of Supersolvable Groups
- Efficient computation of Fourier transforms on compact groups
- Efficient Computation of the Fourier Transform on Finite Groups
- Existence and efficient construction of fast Fourier transforms on supersolvable groups
- Fast Discrete Polynomial Transforms with Applications to Data Analysis for Distance Transitive Graphs
- Fast Fourier analysis for abelian group extensions
- Fast Fourier Analysis for SL2over a Finite Field and Related Numerical Experiments
- Fast Fourier Transforms for Metabelian Groups
- Fast Fourier Transforms for Symmetric Groups: Theory and Implementation
- Fast Fourier transforms for wreath products
- Fast generalized Fourier transforms
- scientific article; zbMATH DE number 3896264 (Why is no real title available?)
- scientific article; zbMATH DE number 3688713 (Why is no real title available?)
- scientific article; zbMATH DE number 3771876 (Why is no real title available?)
- scientific article; zbMATH DE number 44579 (Why is no real title available?)
- scientific article; zbMATH DE number 53765 (Why is no real title available?)
- scientific article; zbMATH DE number 66574 (Why is no real title available?)
- scientific article; zbMATH DE number 67128 (Why is no real title available?)
- scientific article; zbMATH DE number 3552764 (Why is no real title available?)
- scientific article; zbMATH DE number 1263306 (Why is no real title available?)
- scientific article; zbMATH DE number 475357 (Why is no real title available?)
- scientific article; zbMATH DE number 610966 (Why is no real title available?)
- scientific article; zbMATH DE number 1004938 (Why is no real title available?)
- scientific article; zbMATH DE number 1004944 (Why is no real title available?)
- scientific article; zbMATH DE number 1559531 (Why is no real title available?)
- scientific article; zbMATH DE number 3274385 (Why is no real title available?)
- scientific article; zbMATH DE number 3056353 (Why is no real title available?)
- Improved upper complexity bounds for the discrete Fourier transform
- Inductive Limits of Finite Dimensional C ∗ -Algebras
- Is computing with the finite Fourier transform pure or applied mathematics?
- On the algebraic structure of certain partially observable finite-state Markov processes
- Separation of variables and the computation of Fourier transforms on finite groups, I
- Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses
- The efficient computation of Fourier transforms on the symmetric group
Cited in
(11)- Efficient computation of Fourier transforms on compact groups
- Separation of variables and the computation of Fourier transforms on finite groups. II
- The efficient computation of Fourier transforms on semisimple algebras
- Decomposing monomial representations of solvable groups.
- A low-complexity approach to computation of the discrete fractional Fourier transform
- scientific article; zbMATH DE number 910881 (Why is no real title available?)
- Separation of variables and the computation of Fourier transforms on finite groups. II
- Linear time Fourier transforms of \(S_{n-k}\)-invariant functions on the symmetric group \(S_n\)
- Group decomposition by double coset matrices
- Computing double cosets in soluble groups
- Algebraic signal processing theory: Cooley-Tukey type algorithms on the 2-D hexagonal spatial lattice
This page was built for publication: Double coset decompositions and computational harmonic analysis on groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1581065)
