Fast generalized Fourier transforms

DOI10.1016/0304-3975(89)90021-2zbMath0677.65143OpenAlexW1971407031MaRDI QIDQ1123578

Michael Clausen

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90021-2

zbMATH Keywords

fast Fourier transformsdiscrete Fourier transformlinear complexityComputational complexitydiscrete Hadamard- Walsh transformWedderburn's structure theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical methods for integral transforms (65R10) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Numerical methods for trigonometric approximation and interpolation (65T40)

Related Items

Fast Fourier Analysis for SL₂over a Finite Field and Related Numerical Experiments, Quantum Fourier transform over symmetric groups -- improved result, Generating fast Fourier transforms of solvable groups, Computing generalized convolutions faster than brute force, Separation of variables and the computation of Fourier transforms on finite groups. II, Fast Fourier analysis for abelian group extensions, Algebraic signal processing theory: Cooley-Tukey type algorithms on the 2-D hexagonal spatial lattice, Computational bounds for doing harmonic analysis on permutation modules of finite groups, Fast Fourier Transforms for Symmetric Groups: Theory and Implementation, Existence and efficient construction of fast Fourier transforms on supersolvable groups, The efficient computation of Fourier transforms on the symmetric group, Random walks on the BMW monoid: an algebraic approach, Applications of the generalized Fourier transform in numerical linear algebra, Computing Irreducible Representations of Supersolvable Groups, 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, Linear time Fourier transforms of \(S_{n-k}\)-invariant functions on the symmetric group \(S_n\), Unnamed Item, Quantum algorithms for algebraic problems, Efficient Computation of the Fourier Transform on Finite Groups, Canonical bases for cyclotomic fields, Efficient computation of Fourier transforms on compact groups, Double coset decompositions and computational harmonic analysis on groups, Fourier transforms with respect to monomial representations, Improved upper complexity bounds for the discrete Fourier transform

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the computational complexity of the general discrete Fourier transform
• The complexity of group algebra computations
• Young's semi-normal representation of the symmetric group
• Fast Fourier Transforms for Metabelian Groups
• On computing the Discrete Fourier Transform
• Fast Fourier Transforms on Finite Non-Abelian Groups
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Endliche Gruppen I
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform