The multiplicative complexity of the discrete Fourier transform

DOI10.1016/0196-8858(84)90005-8zbMATH Open0568.65096OpenAlexW2060231433MaRDI QIDQ1060552FDOQ1060552

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)

• Title not available (Why is that?)
• 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
• Modified FFTs for Fused Multiply-Add Architectures
• Multiplicative complexity of length-2^mtwo-dimensional discrete cosine transform
• Abelian semi-simple algebras and algorithms for the discrete Fourier transform
• The multiplicative complexity of discrete cosine transforms
• Composite Cyclotomic Fourier Transforms With Reduced Complexities
• Multiplicative characters and the discrete Fourier transform
• On the multiplicative complexity of discrete cosine transforms
• Title not available (Why is that?)
• On algebras related to the discrete cosine transform

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)