The multiplicative complexity of the discrete Fourier transform

DOI10.1016/0196-8858(84)90005-8MaRDI QIDQ1060552zbMATH OpenOpenAlexFDO

Authors Louis Auslander, Ephraim Feig, Shmuel Winograd

Publication date 1984

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-8858(84)90005-8

zbMATH Keywords

discrete Fourier transformmultiplicative complexityminimal algorithms

Mathematics Subject Classification ID

Numerical methods for trigonometric approximation and interpolation (65T40) Analysis of algorithms and problem complexity (68Q25) Trigonometric interpolation (42A15)

Cites work

• Abelian semi-simple algebras and algorithms for the discrete Fourier transform
• On the multiplicative complexity of the discrete Fourier transform
• The multiplicative complexity of certain semilinear systems defined by polynomials

Cited in

(12)

• The multiplicative complexity of discrete cosine transforms
• Abelian semi-simple algebras and algorithms for the discrete Fourier transform
• On algebras related to the discrete cosine transform
• Multiplicative complexity of length-2^mtwo-dimensional discrete cosine transform
• Modified FFTs for Fused Multiply-Add Architectures
• On the multiplicative complexity of discrete cosine transforms
• scientific article; zbMATH DE number 847093 (Why is no real title available?)
• Composite Cyclotomic Fourier Transforms With Reduced Complexities
• Multiplicative characters and the discrete Fourier transform
• scientific article; zbMATH DE number 193953 (Why is no real title available?)
• Algorithms meeting the lower bounds on the multiplicative complexity of length-2/sup n/ DFTs and their connection with practical algorithms
• On the real complexity of a complex DFT

This page was built for publication: The multiplicative complexity of the discrete Fourier transform

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