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 transformminimal algorithmsmultiplicative complexity

Mathematics Subject Classification ID

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

Review text

We show how to compute the multiplicative complexity of the discrete Fourier transform on any set of data points.

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)

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

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)