On the multiplicative complexity of the discrete Fourier transform

DOI10.1016/0001-8708(79)90037-9zbMath0409.68019OpenAlexW2078104849WikidataQ56048274 ScholiaQ56048274MaRDI QIDQ1259162

Shmuel Winograd

Publication date: 1979

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

Full work available at URL: https://doi.org/10.1016/0001-8708(79)90037-9

zbMATH Keywords

Chinese Remainder TheoremAlgebraic ComplexityDiscrete Fourier TansformMultiplicative ComplexityPolynomial Multiplication

Mathematics Subject Classification ID

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

Related Items

Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. I: The algebra \(G[u/<Q(u)^{\ell}>\), \(\ell >1\)], Direct sums of bilinear algorithms, Size bounds for superconcentrators, On the real complexity of a complex DFT, Modified FFTs for Fused Multiply-Add Architectures, The multiplicative complexity of discrete cosine transforms, Unnamed Item, The multiplicative complexity of certain semilinear systems defined by polynomials, Is computing with the finite Fourier transform pure or applied mathematics?, The construction of orthonormal bases diagonalizing the discrete Fourier transform, Ring structure and the Fourier transform, The multiplicative complexity of the discrete Fourier transform, The trade-off between the additive complexity and the asynchronicity of linear and bilinear algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• On Multiplication of Polynomials Modulo a Polynomial
• Some bilinear forms whose multiplicative complexity depends on the field of constants
• On Computing the Discrete Fourier Transform
• Algebras Having Linear Multiplicative Complexities
• An Algorithm for the Machine Calculation of Complex Fourier Series
• On the number of multiplications necessary to compute certain functions