On the computational complexity of the general discrete Fourier transform

DOI10.1016/0304-3975(87)90041-7MaRDI QIDQ1094136zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Recommendations

• Existence and efficient construction of fast Fourier transforms on supersolvable groups
• Publication:4502609
• A new algorithm for fast generalized DFTs
• Generating fast Fourier transforms of solvable groups
• Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses

Cites work

• scientific article; zbMATH DE number 3852384 (Why is no real title available?)
• scientific article; zbMATH DE number 3917702 (Why is no real title available?)
• scientific article; zbMATH DE number 3967873 (Why is no real title available?)
• scientific article; zbMATH DE number 3701095 (Why is no real title available?)
• scientific article; zbMATH DE number 3736029 (Why is no real title available?)
• scientific article; zbMATH DE number 3526920 (Why is no real title available?)
• scientific article; zbMATH DE number 3552764 (Why is no real title available?)
• scientific article; zbMATH DE number 3307642 (Why is no real title available?)
• scientific article; zbMATH DE number 3360363 (Why is no real title available?)
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Analog Scrambling by the General Fast Fourier Transform
• Endliche Gruppen I
• Fast Fourier Transforms on Finite Non-Abelian Groups
• Gaussian elimination is not optimal
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• The complexity of group algebra computations

Cited in

(23)

• Energy Packing Efficiency for the Generalized Discrete Transforms
• Quantum algorithms for algebraic problems
• scientific article; zbMATH DE number 193953 (Why is no real title available?)
• Improved upper complexity bounds for the discrete Fourier transform
• Comments on "Method of flow graph simplification for the 16-point discrete Fourier Transform"
• Algorithms meeting the lower bounds on the multiplicative complexity of length-2/sup n/ DFTs and their connection with practical algorithms
• Fast generalized Fourier transforms
• Implementation of group-covariant positive operator valued measures by orthogonal measurements
• On the real complexity of a complex DFT
• Generating fast Fourier transforms of solvable groups
• Efficient Computation of the Fourier Transform on Finite Groups
• Existence and efficient construction of fast Fourier transforms on supersolvable groups
• Representation-theoretical properties of the approximate quantum Fourier transform
• A new algorithm for fast generalized DFTs
• The efficient computation of Fourier transforms on semisimple algebras
• A fast generalized DFT for finite groups of Lie type
• A generalized FFT for Clifford algebras
• Generalizing the discrete Fourier transform
• Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses
• scientific article; zbMATH DE number 4189089 (Why is no real title available?)
• On the multiplicative complexity of discrete cosine transforms
• scientific article; zbMATH DE number 847093 (Why is no real title available?)
• On computation of certain discrete Fourier transforms using binary calculus

Describes a project that uses

Uses Software

• REPSN

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

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