Improved upper complexity bounds for the discrete Fourier transform

DOI10.1007/BF01810853zbMath0734.65103OpenAlexW2019435258MaRDI QIDQ811112

Benno Tietz, Ulrich Baum, Michael Clausen

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

fast Fourier transformgroup algebradiscrete Fourier transformlinear complexity

Mathematics Subject Classification ID

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

Related Items (5)

Fast Fourier Analysis for SL₂over a Finite Field and Related Numerical Experiments ⋮ Existence and efficient construction of fast Fourier transforms on supersolvable groups ⋮ The efficient computation of Fourier transforms on semisimple algebras ⋮ Double coset decompositions and computational harmonic analysis on groups ⋮ Variations on computing reciprocals of power series

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast Fourier analysis for abelian group extensions
• On the computational complexity of the general discrete Fourier transform
• Fast generalized Fourier transforms
• Fast Fourier transform and convolution algorithms
• The complexity of group algebra computations
• A generalization of spectral analysis with application to ranked data
• Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses
• Efficient Computation of the Fourier Transform on Finite Groups
• 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

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