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\)
From MaRDI portal
Publication:1110328
DOI10.1016/0304-3975(88)90017-5zbMath0656.68040MaRDI QIDQ1110328
Zvi Galil, Shmuel Winograd, Amir Z. Averbuch
Publication date: 1988
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(88)90017-5
68Q25: Analysis of algorithms and problem complexity
68W30: Symbolic computation and algebraic computation
12E05: Polynomials in general fields (irreducibility, etc.)
12-04: Software, source code, etc. for problems pertaining to field theory
Related Items
Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. II: The algebra \(G[u/\langle{} u^ n \rangle\)], A lower bound for the multiplication of polynomials modulo a polynomial, On the direct sum conjecture in the straight line model, Multiplicative complexity of direct sums of quadratic systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On varieties of optimal algorithms for the computation of bilinear mappings. I. The isotropy group of a bilinear mapping
- On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for \(2\times 2\)-matrix multiplication
- On varieties of optimal algorithms for the computation of bilinear mappings. III. Optimal algorithms for the computation of \(xy\) and \(yx\) where \(x,y\in M_2(K)\)
- On multiplication in algebraic extension fields
- On the multiplicative complexity of the discrete Fourier transform
- Certain systems of bilinear forms whose minimal algorithms are all quadratic
- On systems of bilinear forms whose minimal division-free algorithms are all bilinear
- Some bilinear forms whose multiplicative complexity depends on the field of constants
- On Computing the Discrete Fourier Transform
- Algebras Having Linear Multiplicative Complexities
- On the number of multiplications necessary to compute certain functions
