Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multivariate polynomials with the same $x_i$-terms with maximal total degree $\delta$, but with different coefficients in $R$. How fast can we compute the product of $f$ and $g$, i.e. the resulting coefficients of each term?

For univariate multiplication in a general setting like this, one can use variants of schonhage-strassen to achieve $O(\delta \log \delta \log\log \delta)$ (e.g. Theorem 8.23 in von zur Gathen & Gerhard, Modern Computer Algebra).

I have only been able to find a non-trivial algorithm for when $R$ is a field of characteristic 0, but not for $R$ being a general commutative ring.

  • 1
    $\begingroup$ The number of degree $d$ multivariate monomials is exponential in $d$, so how exactly do you represent the input and output polynomials? In the most obvious representation by a list of nonzero monomials, you cannot beat the trivial quadratic algorithm, as the number of monomials in the output can be that high (consider e.g. $(x^d+x^{d-1}+\dots+1)(y^d+y^{d-1}+\dots+1)$). $\endgroup$ – Emil Jeřábek Jun 15 '15 at 9:22
  • $\begingroup$ Thanks for pointing out this flaw in the question. In my case the x-terms of $f$ and $g$ are actually the same, but the coefficients are not. Will update the question to cover that. $\endgroup$ – Chiel ten Brinke Jun 15 '15 at 11:34
  • $\begingroup$ The edit did nothing to clarify the question, so let me ask again: what is the representation of input and output? $\endgroup$ – Emil Jeřábek Jun 15 '15 at 20:58
  • $\begingroup$ A list of monomials indeed. $\endgroup$ – Chiel ten Brinke Jun 15 '15 at 21:35
  • $\begingroup$ As I already explained in the first comment, with a list of monomials you cannot do better than the trivial quadratic algorithm. The additional restriction is of no consequence, you can take e.g. $(x^d+\dots+x+y^d+\dots+y+1)^2$. $\endgroup$ – Emil Jeřábek Jun 16 '15 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.