On the computational complexity of the general discrete Fourier transform

DOI10.1016/0304-3975(87)90041-7zbMATH Open0629.68041OpenAlexW1964153492WikidataQ127676224 ScholiaQ127676224MaRDI QIDQ1094136FDOQ1094136

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

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

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)

Cites Work

• An Algorithm for the Machine Calculation of Complex Fourier Series
• Title not available (Why is that?)
• Gaussian elimination is not optimal
• Title not available (Why is that?)
• Title not available (Why is that?)
• Endliche Gruppen I
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast Fourier Transforms on Finite Non-Abelian Groups
• The complexity of group algebra computations
• Title not available (Why is that?)
• Analog Scrambling by the General Fast Fourier Transform

Cited In (23)

• Title not available (Why is that?)
• Comments on "Method of flow graph simplification for the 16-point discrete Fourier Transform"
• Improved upper complexity bounds for the 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
• Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses
• Generalizing the discrete Fourier transform
• Title not available (Why is that?)
• On the multiplicative complexity of discrete cosine transforms
• Title not available (Why is that?)
• Energy Packing Efficiency for the Generalized Discrete Transforms
• On computation of certain discrete Fourier transforms using binary calculus
• Quantum algorithms for algebraic problems

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)