# What is the complexity of multivariate gcd?

I have by now seen some algorithms to compute the gcd of two multivariate polynomials from $\mathbb{Z}[x_1,...,x_k]$, but what I am really looking for are statements about the general complexity of the problem. All I could find so far was that it seems to be considered bad, and one should avoid gcd-computations if possible.

But how bad is it actually? Are there any known upper or lower bounds?

Edit: The simplest algorithm I found is to recursively use the Euclidean algorithm for univariate polynomials on $\mathbb{Z}[x_1,...,x_{k-1}][x_k]$ and then for the coefficients $\mathbb{Z}[x_1,...,x_{k-2}][x_{k-1}]$ and so on. I'm already not quite clear on what the complexity of this algorithm is. I can also not imagine that there is no better way to do it.

There are several algorithms to compute the gcd of two multivariate polynomials over rings. I'll mention an algorithm by Zippel which is widely used.

Zippel's Algorithm [1]

This is a probabilistic algorithm which uses a combination of dense and sparse interpolation to construct the GCD of polynomials. It is based on the observation that evaluating a polynomial at a random point will almost never yield zero (Schwartz-Zippel lemma) [1]. So, if a coefficient is determined to be zero somewhere in the interpolation process, the algorithm assumes it to be zero everywhere.

Zippel's Algorithm requires a bound on partial degree in each variable $d$ as an input. We substitute randomly chosen integers (starting point) for all but one variable. The solution is built up by interpolating for one variable at a time.The first polynomial produced involving a particular variable is done via dense interpolation. This polynomial is then used as a skeleton for a number of sparse interpolation. These sparse interpolations are used to introduce the next variable. After finding GCD modulo a prime, we treat it as a skeleton for finding the GCD modulo some other prime. The final polynomial is constructed using Chinese Remainder Algorithm.

The correctness algorithm depends on the accuracy of the skeletal polynomials. Skeletal polynomials will have missing terms if some coefficients are zero at the starting point. But this happens rarely as the total number of zeros are bounded by Schwartz-Zippel lemma, which states that if the integers in starting point are chosen from a subset $\mathbb{S}$ of a field, then probability of a coefficient being zero is bounded by $d/|\mathbb{S}|$, where $d$ is the total degree of the coefficient.

The algorithm performs $O(ndt)$ evaluations for the interpolation process and runs in $O(ndt^3)$ operations, where n is the number of variables, d is the degree in each variable and t is the number of terms in the final polynomial. The algorithm still has some issues which can be found in [2] along with the ways in which they have been resolved.

Take a look at [3] for a deterministic algorithm by Ben-Or and Tivari.

[1] Zippel, Richard. ”Probabilistic algorithms for sparse polynomials.” Symbolic and algebraic computation (1979): 216-226.

[2] de Kleine, Jennifer, Michael Monagan, and Allan Wittkopf. ”Algorithms for the Non-monic case of the Sparse Modular GCD Algorithm.” Proceedings of the 2005 international symposium on Symbolic and algebraic computation. ACM, 2005.

[3] Ben-Or, Michael, and Prasoon Tiwari. ”A deterministic algorithm for sparse multivariate polynomial interpolation.” Proceedings of the twentieth annual ACM symposium on Theory of computing. ACM, 1988.