Bivariate Polynomial Multiplication

We study the multiplicative complexity and the rank of the multiplication in the local algebras R/sub m, n/=k[x, y]/(x/sup m+1/, y/sup n+1/) and T/sub n/=k[x, y]/(x/sup n+1/, x/sup n/y, .. ., y/sup n+1/) of bivariate polynomials. We obtain the lower bounds (21/3-0(1))/spl middot/dim R/sub m, n/, and (2 1/2 -0(1))/spl middot/dim T/sub n/ for the multiplicative complexity of the multiplication in R/sub m, n/ and T/sub n/, respectively. On the other hand, we derive the upper bounds 3/spl middot/dim T/sub n/-2n-2 and 3/spl middot/dim R/sub m. n/-m-n-3 for the rank of the multiplication in T/sub n/ and R/sub m, n/, respectively, provided that the ground field k admits "fast" univariate polynomial multiplication mod x/sup N/-1. Our results are also applicable to arbitrary finite dimensional algebras of truncated bivariate polynomials k[x, y]/I, where the ideal I=(x(d/sub 0/+1), x(d/sub 1/+1)y, .. ., x(d/sub n/+1)y/sup n/, y/sup n+1/) is described by a degree pattern d/sub 0//spl ges/d/sub 1//spl ges//spl middot//spl middot//spl middot//spl ges/d/sub n//spl ges/0.

Authors

• Markus Bläser

Keywords

• Polynomials
• Algebra
• Radio access networks
• Upper bound
• Tellurium
• Shape
• Costs
• Performance evaluation
• Polynomial Multiplication
• Multiple Complex
• Univariate Polynomial
• Ground Field
• General Case
• Vector Space
• Monomial
• N Forms
• Arbitrary Precision
• Monomorphism
• Maximal Ideal
• Canonical Projection