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\)

DOI10.1016/0304-3975(88)90017-5zbMath0656.68040OpenAlexW2060449504MaRDI 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

zbMATH Keywords

algebraic complexityminimal bilinear algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials in general fields (irreducibility, etc.) (12E05) Software, source code, etc. for problems pertaining to field theory (12-04)

Related Items (4)

Multiplicative complexity of direct sums of quadratic systems ⋮ 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

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

This page was built for publication: 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\)