Improved upper complexity bounds for the discrete Fourier transform

DOI10.1007/BF01810853MaRDI QIDQ811112zbMATH OpenOpenAlexFDO

Authors Ulrich Baum, Michael Clausen, Benno Tietz

Publication date 1991

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01810853

zbMATH Keywords

discrete Fourier transformfast Fourier transformgroup algebralinear complexity

Mathematics Subject Classification ID

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

Review text

By investigating several classical fast Fourier transform algorithms, this paper evaluates the upper bounds \(L_ 2(G)|_{\max}\), such that \(L_ 2(G)|_{\max}\leq 8| G| \log_ 2| G|\) in the discrete Fourier transform on any finite metabelian group G.

Recommendations

• Fast Fourier Transforms for Metabelian Groups
• On the computational complexity of the general discrete Fourier transform
• Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses
• Fast generalized Fourier transforms
• Separation of variables and the computation of Fourier transforms on finite groups, I

Cites work

• A generalization of spectral analysis with application to ranked data
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Efficient Computation of the Fourier Transform on Finite Groups
• Endliche Gruppen I
• Fast Fourier analysis for abelian group extensions
• Fast Fourier transform and convolution algorithms
• Fast Fourier Transforms for Metabelian Groups
• Fast Fourier Transforms on Finite Non-Abelian Groups
• Fast generalized Fourier transforms
• scientific article; zbMATH DE number 4014644 (Why is no real title available?)
• scientific article; zbMATH DE number 3852384 (Why is no real title available?)
• scientific article; zbMATH DE number 3896264 (Why is no real title available?)
• scientific article; zbMATH DE number 4023201 (Why is no real title available?)
• scientific article; zbMATH DE number 3688713 (Why is no real title available?)
• scientific article; zbMATH DE number 4112856 (Why is no real title available?)
• On computing the Discrete Fourier Transform
• On the computational complexity of the general discrete Fourier transform
• Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses
• The complexity of group algebra computations

Cited in

(10)

• Double coset decompositions and computational harmonic analysis on groups
• Variations on computing reciprocals of power series
• On the real complexity of a complex DFT
• The efficient computation of Fourier transforms on semisimple algebras
• Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses
• Fast Fourier Transforms for Metabelian Groups
• Energy Packing Efficiency for the Generalized Discrete Transforms
• Upper and Lower Bounds on Time-Space Tradeoffs for Computations with Embedded Fast Fourier Transforms
• Fast Fourier Analysis for SL₂over a Finite Field and Related Numerical Experiments
• Existence and efficient construction of fast Fourier transforms on supersolvable groups

This page was built for publication: Improved upper complexity bounds for the discrete Fourier transform

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