On the multiplicative complexity of the discrete Fourier transform
From MaRDI portal
Publication:1259162
DOI10.1016/0001-8708(79)90037-9zbMath0409.68019WikidataQ56048274 ScholiaQ56048274MaRDI QIDQ1259162
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
Chinese Remainder Theorem; Algebraic Complexity; Discrete Fourier Tansform; Multiplicative Complexity; Polynomial Multiplication
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