On the multiplicative complexity of the discrete Fourier transform

DOI10.1016/0001-8708(79)90037-9zbMath0409.68019WikidataQ56048274 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 Theorem; Algebraic Complexity; Discrete Fourier Tansform; Multiplicative Complexity; Polynomial Multiplication

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

65T40: Numerical methods for trigonometric approximation and interpolation

Related Items

Modified FFTs for Fused Multiply-Add Architectures, Unnamed Item, The multiplicative complexity of certain semilinear systems defined by polynomials, 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, 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, The multiplicative complexity of discrete cosine transforms, Is computing with the finite Fourier transform pure or applied mathematics?

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