Generating fast Fourier transforms of solvable groups

DOI10.1016/J.JSC.2002.06.006MaRDI QIDQ597054zbMATH OpenOpenAlexFDO

Authors Michael Clausen, Meinard Müller

Publication date 6 August 2004

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jsc.2002.06.006

zbMATH Keywords

complexity boundsdiscrete Fourier transformfast Fourier transformsolvable groups

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Complexity and performance of numerical algorithms (65Y20)

Review text

The authors present a new algorithm for constructing a complete list of pairwise inequivalent ordinary irreducible representations of a finite solvable group \(G\). They give a rough analysis and worst-case complexity bounds. The output of the algorithm is well suited to performing a fast Fourier transform of \(G\). For supersolvable groups the disrete Fourier transform generation is much easier and can be done in a time which is --- up to logarithmic factors --- propontial to the output length. The authors also report on a recent implementation for the case of supersolvable groups.

Recommendations

• Existence and efficient construction of fast Fourier transforms on supersolvable groups
• Efficient Computation of the Fourier Transform on Finite Groups
• Publication:4502609
• Decomposing monomial representations of solvable groups.
• On the computational complexity of the general discrete Fourier transform

Cites work

• Computing Irreducible Representations of Supersolvable Groups
• Efficient Computation of the Fourier Transform on Finite Groups
• Endliche Gruppen I
• Existence and efficient construction of fast Fourier transforms on supersolvable groups
• Fast generalized Fourier transforms
• Gaussian elimination is not optimal
• scientific article; zbMATH DE number 3526920 (Why is no real title available?)
• scientific article; zbMATH DE number 610966 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1004938 (Why is no real title available?)
• scientific article; zbMATH DE number 1504649 (Why is no real title available?)
• On the computational complexity of the general discrete Fourier transform
• Towards a soluble quotient algorithm

Cited in

(11)

• On the computational complexity of the general discrete Fourier transform
• DFT-based word normalization in finite supersolvable groups.
• Decomposing monomial representations of solvable groups.
• Subquadratic-time algorithms for normal bases
• Applications of the generalized Fourier transform in numerical linear algebra
• Efficient Computation of the Fourier Transform on Finite Groups
• Construction of group transforms subject to several performance criteria
• Computing Irreducible Representations of Supersolvable Groups
• scientific article; zbMATH DE number 1504649 (Why is no real title available?)
• Existence and efficient construction of fast Fourier transforms on supersolvable groups
• Fast group-theoretical transform

Describes a project that uses

Uses Software

• AREP

This page was built for publication: Generating fast Fourier transforms of solvable groups

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