1
$\begingroup$

If I am asked to find the roots of a polynomial of one variable, I will use a computer to estimate the eigenvalues of its companion matrix. Now suppose I'm given a real polynomial of multiple variables, and I'm promised that the roots form a discrete set. Is there a similarly fast and stable way to find the roots? Considering Denis Serre's answer to this question, I doubt Newton's method will be as helpful.

$\endgroup$
2
  • 5
    $\begingroup$ This question is a little subtle because the property of having isolated real roots is not stable. Perturb it one way and the root disappears. Perturb it the other way and the root expands into a sphere of roots. That, said, at an isolated real zero, all the partial derivatives vanish. Thus I would search for locations where all partial derivatives vanish. So I think the question is very much related to finding common zeroes of $n$ polynomials in $n$ variables - which you can actually use Newton's method for! A similar way to find all the common zeroes is not obvious, though. $\endgroup$
    – Will Sawin
    Aug 11, 2013 at 3:36
  • $\begingroup$ You could apply gloptipoly to the squared polynomial. $\endgroup$ Oct 7, 2013 at 9:56

2 Answers 2

4
$\begingroup$

Gröbner basis methods will help you find all roots. There is no efficient method, though; all methods have really bad worst-case complexity.

$\endgroup$
2
$\begingroup$

For polynomials with rational coefficients, the cylindrical decomposition in real algebric geometry gives a way to find whether a polynomial (or system of polynomials) has finitely many roots in $\mathbb{R}^n$ or not, and if it has, it can compute the coordinates of each root, in the form of the root of a single-variable polynomial (and specify which root by giving the sign of all derivatives, by the Thom encoding). A reference is the book Algorithms in real algebraic geometry by Basu-Pollack-Roy.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.