Jenkins-Traub algorithm to find the zeros of a multiple-variable polynomial

Question

The Jenkins–Traub algorithm for polynomial zeros is a fast globally convergent iterative method published in 1970 by Michael A. Jenkins and Joseph F. Traub.

The published algorithm, e.g. https://dl.acm.org/citation.cfm?id=355643, deals with polynomials of a single variable. I wonder whether the algorithm has never been applied on multivariate polynomials. I do not find any of such kind of applications in the literature.

My question is: What are the difficulties for finding roots of a multi-variable polynomial? In other words, why you can apply Jenkins-Traub on $f(x)=x^2 - 1$ but not on $f(x,y)=x^2+y^2 - 1$. If I understand correctly, a key step of Jenkins-Traub is to iteratively divide the underlying polynomial by (x-r) where r is a root. I felt that you could do polynomial division on multivariate polynomials as well for the purpose of root-finding. I probably misunderstood something somewhere.

Answer 1

No chance. Solving for the roots of multivariate polynomials is a completely different beast from the univariate case.

For one thing, a multivariate polynomial will typically be zero on entire curves, and not just at isolated points (consider dxiv's $x^2+y^2-1$ for instance). So usually one seeks to reduce systems of polynomial equations, rather than just looking at one equation.

There are some computational techniques for solving such systems, based on constructing Groebner bases. These techniques are extremely expensive and, as far as I know, not nearly as widely used as single-variable solvers like Jenkins-Traub. In practice when finding only a single root is required, (quasi)-Newton methods are used.

Answer 2

If one allows complex solutions also, you could take all but one of the variables constant and use one of the root finding algorithms for polynomial in a single variable over the field of complex numbers.

Answer 3

The fundamental fact behind the construction of Jenkins-Traub, as well as some other methods like Durand-Kerner and Bairstow, is the fundamental theorem of algebra, that the set of roots corresponds to a complete, unique factorization of the polynomial into linear factors, or linear and quadratic factors if restricted to real coefficients.

For Jenkins-Traub CPOLY, the factorization $$ P(X)=(X-\alpha)\bar H(X) $$ is interpreted as an eigenvalue equation $$ X\cdot \bar H(X)=\alpha\bar H(X)\pmod{P(X)}. $$ Then linear algebra methods are applied, here variants of the shifted inverse power iteration, primarily to improve the coefficient vector of $\bar H$, with the root approximation improving as a consequence.

Weierstraß-Durand-Kerner is based on the full factorization, starting with some random product and improving all factors, and thus the roots, simultaneously. (Which turns out to be a multivariate Newton method with all properties and consequences.)

Polynomial systems do not have a similar factorization. The conceptually closest idea is the decomposition into irreducible components. But, as far as I know, such a decomposition is the result of a full analysis of the system, not a simplification in the solution process similar to the deflation strategy in the univariate case.

---

In contrast the Newton method, Halley's method etc. are primarily based on function values and derivatives in one point and the resulting low-degree approximation of the function close to this point and its roots. This all generalizes nicely to higher dimension, at least in concept. There is still a difference in global convergence.