1

Given two large multivariate polynomials $f$ and $g$ in $m$ variables of degree $n$, which are factorized and have i.e. more than a 1000 terms, how can we check efficiently if they are the same?

To compare the coefficients, one would need to compute the coefficients, but I think expanding the polynomials can lead to too many terms to compute in reasonable time. Is there a smarter way? Or is this impossible because it is a necessity to check all coefficients?

Drakes
  • 73
  • Are the polynomials partially factorized or complete factorized ? If they are factorized into irreducible factors, the polynomials are equivalent if and only if they contain the same factors with the same multiplicity. – Peter May 31 '16 at 09:57

2 Answers2

1

Two UNIVARIATE polynomials of degree $n$ are identical, if they coincide at $n+1$ places, for example at the numbers $0,...,n$.

To formulate it more mathematically, if $f(n)=g(n)$ for $n=0,...,d\ $ and $deg(f)=deg(g)=d\ $, then we can conculde $f=g$.

This can be easily checked even for monster polynomials.

If we have two variables (lets say $x$ and $y$), we can fix $x$ and get a univariate polynomial. If the polynomial has degree $d$ with respect to $x$, I think we can also use the above idea, but I am not sure, whether it actually works.

If yes, we could use the method for arbitary polynomials.

In practice you could also do the following :

Evaluate the difference of the polynomials at some random points.

If the value is not $0$ at any point, the polynomials must be distinct.

If you get $0$ at all the points, you have a very good chance that the polynomials are equal.

Maybe, from a mathematical point of view, this method is debateable. But it should be sufficient for practical purpose.

Peter
  • 84,454
  • But what about multivariate polynomials? – Servaes May 31 '16 at 09:38
  • The idea behind this is, is that polynomials are linear in their coefficients, thus by evaluating them you get a constraint for a linear system of equations on the coefficients. One evaluation gives you one constraint, thus one would need a linear number of evaluations in the number of coefficients to fully "specify" the polynomials, I guess. But I'm still hoping for a better solution as the input size can be smaller than the number of coefficients. – Drakes May 31 '16 at 09:55
1

That essentially means that you want to solve the notoriously hard problem of polynomial identity testing in a setting where the polynomials are given as algebraic circuits (consisting of "formulas" for the factors). Any progress there is warmly welcome, because a large community of world-class researchers hardly made any breakthroughs in the past dozen years or so, at least from a practical perspective. To the best of my knowledge, it's also one of the big, big open problems where we do not even have a good idea about its place in the computational complexity hierarchy except for highly restricted settings.

Peter's idea is that you should evaluate and compare both polynomials on an unisolvent point set such as the Padua points. Unfortunately, determining a (small) such set is non-trivial in general, to say the least.

The practitioner's solution to that: rely on the Schwartz-Zippel lemma and plug in as many random points as necessary until the probability of a false positive is low enough. E.g., $10^{-10}$ times your estimate on the combined probability that there is a sudden earthquake destroying your machine, a bit flip due to radiation, a compiler bug that spoils some fancier algorithm, or (if all that's too small) the probability that you introduce a bug while you implement or design that algorithm...

Seriously.

akobel
  • 700
  • 4
  • 7