<p>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 <a href="https://math.stackexchange.com/questions/408491/total-degree-of-a-polynomial">total degree</a> $\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?</p>

<p>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 &amp; Gerhard, Modern Computer Algebra).</p>

<p>I have only been able to find a <a href="http://dl.acm.org/citation.cfm?id=74556" rel="nofollow noreferrer">non-trivial algorithm</a> for when $R$ is a field of characteristic 0, but not for $R$ being a general commutative ring.</p>

CC BY-SA 3.0
2015-06-15T09:22:53.617Z
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)$).
Emil Jeřábek
CC BY-SA 3.0
2015-06-15T11:34:57.940Z
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.
chtenb
CC BY-SA 3.0
2015-06-15T20:58:43.577Z
The edit did nothing to clarify the question, so let me ask again: what is the representation of input and output?
Emil Jeřábek
CC BY-SA 3.0
2015-06-15T21:35:59.613Z
A list of monomials indeed.
chtenb
CC BY-SA 3.0
2015-06-16T08:27:09.860Z
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$.
Emil Jeřábek
CC BY-SA 3.0
2015-06-16T09:24:16.623Z
Actually, you cannot beat the quadratic algoritm even for *univariate* polynomials in this (= sparse) representation. Fix $n$, and let $f$ be the sum of all monomials $x^j$ s.t. $j\le n^2$, and all even-position bits in the binary expansion of $j$ are $0$. Let $g$ be defined similarly, but with odd positions instead of even. Then $f$ and $g$ have size $O(n)$, but $fg$ has size $O(n^2)$. The same goes for $(f+g)(f+g)$.
Emil Jeřábek
CC BY-SA 3.0
2015-06-16T09:33:40.990Z
Which reminds me that your question seems to implicitly suggest that you want to measure running time in terms of the degree. This doesn't make sense for multivariate polynomials. For one thing, you cannot multiply linear polynomials like $x_1+\dots+x_n$ in *constant* time. Even if the bound were allowed to also depend on the number of variables, it couldn't be better than exponential, as already the input may have so many monomials. The only sensible thing is to measure run time in terms of the actual size of the input (as elsewhere in TCS).
Emil Jeřábek
CC BY-SA 3.0
2015-06-16T10:12:58.387Z
First, it might have been a bad call to use 'total degree' instead of a fixed maximal degree $\delta$ for each variable. If we do the latter, I believe the naieve algorithm uses $\delta^{2n}$. Why would it not be possible to improve it to something like $\delta^n \cdot n \delta \dots$?
chtenb
CC BY-SA 3.0
2015-06-16T10:15:31.577Z
As a reference, in this paper something similar is done, but only for structures that allow FFT: http://dl.acm.org/citation.cfm?id=806332
chtenb
CC BY-SA 3.0
2015-06-16T11:51:39.243Z
Sigh. That’s a rather different representation, you are effectively listing all coefficients (zero or not) in a MAXLEX order. You really need to write the exact details of the setup into the question, as well as some motivation why you care about the exact exponent in the already exponential bound. Anyway, the trivial lower bound given by the output size in this case is $(2d+1)^n$. OTOH, Kronecker substitution $x_i\mapsto x^{(2d+1)^{i-1}}$ combined with univariate polynomial multiplication takes $O((2d+1)^nn(\log d)(\log n+\log\log d))$ operations, so that’s optimal up to logarithmic factors.
Emil Jeřábek
CC BY-SA 3.0
2015-06-16T12:05:11.230Z
The Moenck paper says more or less the same, actually. So why does it not answer your question?
Emil Jeřábek
CC BY-SA 3.0
2015-06-16T12:22:25.670Z
Thanks for your answer. My apologies for not realizing the implications of the different representations. If the Kronecker trick yields the fastest asymptotic running time available, then that indeed answers my question. But if there have been better insights than this since 1976, I would like to know.
chtenb
<co.combinatorics><polynomials><convolution>
Algorithm for multiplying multivariate polynomials in a commutative ring
chtenb
# Algorithm for multiplying multivariate polynomials in a commutative ring

(Asked by: username_0 on 2015-06-15)

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](https://math.stackexchange.com/questions/408491/total-degree-of-a-polynomial) $\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](http://dl.acm.org/citation.cfm?id=74556) for when $R$ is a field of characteristic 0, but not for $R$ being a general commutative ring.

**Tags:** co.combinatorics, polynomials, convolution

> **Comments:**
> **username_1**: 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)$).  
> **username_0**: 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.  
> **username_1**: The edit did nothing to clarify the question, so let me ask again: what is the representation of input and output?  
> **username_0**: A list of monomials indeed.  
> **username_1**: 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$.  
> **username_1**: Actually, you cannot beat the quadratic algoritm even for *univariate* polynomials in this (= sparse) representation. Fix $n$, and let $f$ be the sum of all monomials $x^j$ s.t. $j\le n^2$, and all even-position bits in the binary expansion of $j$ are $0$. Let $g$ be defined similarly, but with odd positions instead of even. Then $f$ and $g$ have size $O(n)$, but $fg$ has size $O(n^2)$. The same goes for $(f+g)(f+g)$.  
> **username_1**: Which reminds me that your question seems to implicitly suggest that you want to measure running time in terms of the degree. This doesn't make sense for multivariate polynomials. For one thing, you cannot multiply linear polynomials like $x_1+\dots+x_n$ in *constant* time. Even if the bound were allowed to also depend on the number of variables, it couldn't be better than exponential, as already the input may have so many monomials. The only sensible thing is to measure run time in terms of the actual size of the input (as elsewhere in TCS).  
> **username_0**: First, it might have been a bad call to use 'total degree' instead of a fixed maximal degree $\delta$ for each variable. If we do the latter, I believe the naieve algorithm uses $\delta^{2n}$. Why would it not be possible to improve it to something like $\delta^n \cdot n \delta \dots$?  
> **username_0**: As a reference, in this paper something similar is done, but only for structures that allow FFT: http://dl.acm.org/citation.cfm?id=806332  
> **username_1**: Sigh. That’s a rather different representation, you are effectively listing all coefficients (zero or not) in a MAXLEX order. You really need to write the exact details of the setup into the question, as well as some motivation why you care about the exact exponent in the already exponential bound. Anyway, the trivial lower bound given by the output size in this case is $(2d+1)^n$. OTOH, Kronecker substitution $x_i\mapsto x^{(2d+1)^{i-1}}$ combined with univariate polynomial multiplication takes $O((2d+1)^nn(\log d)(\log n+\log\log d))$ operations, so that’s optimal up to logarithmic factors.  
> **username_1**: The Moenck paper says more or less the same, actually. So why does it not answer your question?  
> **username_0**: Thanks for your answer. My apologies for not realizing the implications of the different representations. If the Kronecker trick yields the fastest asymptotic running time available, then that indeed answers my question. But if there have been better insights than this since 1976, I would like to know.  

---

## 0 answers

