Fast computation of discrete Fourier transforms using polynomial transforms

DOI10.1109/TASSP.1979.1163216MaRDI QIDQ3886825zbMATH OpenOpenAlexFDO

Authors Henri J. Nussbaumer, Philippe Quandalle

Publication date 1979

Published in IEEE Transactions on Acoustics, Speech, and Signal Processing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tassp.1979.1163216

zbMATH Keywords

efficient algorithmsfast Fourier transformflow-chartsminimum number of operationspolynomial transformsshort-length algorithmstablestwo-dimensional discrete Fourier transformWinograd Fourier TransformWinograd's method

Mathematics Subject Classification ID

Trigonometric interpolation (42A15) Signal detection and filtering (aspects of stochastic processes) (60G35) Numerical methods for trigonometric approximation and interpolation (65T40) Analysis of algorithms and problem complexity (68Q25)

Cited in

(9)

• A note on prime factor FFT algorithms
• Abelian semi-simple algebras and algorithms for the discrete Fourier transform
• Index transforms for N-dimensional DFT's
• The inverse of an automorphism in polynomial time
• 2-D FFT algorithm by matrix factorization in a 2-D space
• Vector coding algorithms for multidimensional discrete Fourier transform
• Integer multiplication in time \(O(n\log n)\)
• Modified FFTs for Fused Multiply-Add Architectures
• Group Convolutions and Matrix Transforms

This page was built for publication: Fast computation of discrete Fourier transforms using polynomial transforms

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