On the computational complexity of the general discrete Fourier transform

DOI10.1016/0304-3975(87)90041-7zbMath0629.68041OpenAlexW1964153492WikidataQ127676224 ScholiaQ127676224MaRDI QIDQ1094136

Thomas Beth

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90041-7

zbMATH Keywords

solvable groupgroup algebras of finite groupsasymptotic complexitiesGeneral Discrete Fourier Transform

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Numerical methods for trigonometric approximation and interpolation (65T40)

Related Items (9)

Generating fast Fourier transforms of solvable groups ⋮ Fast generalized Fourier transforms ⋮ Representation-theoretical properties of the approximate quantum Fourier transform ⋮ Existence and efficient construction of fast Fourier transforms on supersolvable groups ⋮ Implementation of group-covariant positive operator valued measures by orthogonal measurements ⋮ The efficient computation of Fourier transforms on semisimple algebras ⋮ Quantum algorithms for algebraic problems ⋮ Efficient Computation of the Fourier Transform on Finite Groups ⋮ Improved upper complexity bounds for the discrete Fourier transform

Uses Software

• REPSN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of group algebra computations
• Gaussian elimination is not optimal
• Fast Fourier Transforms on Finite Non-Abelian Groups
• Analog Scrambling by the General Fast Fourier Transform
• 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

This page was built for publication: On the computational complexity of the general discrete Fourier transform