\input zb-basic
\input zb-ioport
\iteman{io-port 01057738}
\itemau{Sch\"onhage, Arnold}
\itemti{Bivariate polynomial multiplication patterns.}
\itemso{Cohen, G\'erard (ed.) et al., Applied algebra, algebraic algorithms and error-correcting codes. 11th international symposium, AAECC-11, Paris, France, July 17-22, 1995. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 948, 70-81 (1995).}
\itemab
Summary: Motivated by multiplication of numerical univariate polynomials with various kinds of truncations, the author studies corresponding bivariate problems $A(x,y) B(x,y)= C(x,y)$ in the algebraic setting with indeterminate coefficients over suitable ground fields, counting essential multiplications only. The rectangular case concerning factors $A,B$ with entries $x^iy^j$ for $i\leq n$, $j\leq m$, e.g. with $m=n$, has complexity $(2n+1)^2$. Here multiplication with single truncation, computing the product $C(x,y)\bmod x^{n+1}$, or $\text{mod } y^{n+1}$, seems still to have the same full multiplication complexity, as is well-known for the univariate case, while the double truncation case $\text{mod} (x^{n+1}, y^{n+1})$ admits the reduced upper bound $3n^2+ 4n+1$, opposed to a lower bound of $2n^2+ 4n+1$. There is a similar saving factor for the triangular case with factors $A,B$ of total degree $n$ to be multiplied $\text{mod} (x^{n+1}, x^ny,\dots, y^{n+1})$. The issue remains of finding the exact complexities of these multiplication problems.
\itemrv{~}
\itemcc{}
\itemut{bivariate polynomials; multiplication complexity; truncation}
\itemli{}
\end