Fast computation of discrete Fourier transforms using polynomial transforms

DOI10.1109/TASSP.1979.1163216zbMath0443.65109OpenAlexW2167872248MaRDI QIDQ3886825

Philippe Quandalle, Henri J. Nussbaumer

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

tablesfast Fourier transformefficient algorithmspolynomial transformstwo-dimensional discrete Fourier transformWinograd Fourier Transformminimum number of operationsflow-chartsshort-length algorithmsWinograd's method

Mathematics Subject Classification ID

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

Related Items

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