I want to numerically find all the roots of a system of polynomials (n equations in n variables). Since I can compute the Jacobian for the system (analytically or otherwise), I can use the Newton Raphson method to find a single root (e.g. as described in the Numerical Recipes book).

How do I find the other roots (if they exist), either using a different algorithm or extending the Newton Raphson method? If this is not always possible, what about finding all the roots in a bounded interval [a,b]? Other roots may exist, but I only need to find the ones that lie in the interval - however, it is possible for multiple roots to lie in the interval?


  • 2
    $\begingroup$ This is a much studied topic, see, eg., en.wikipedia.org/wiki/…. Try netlib.org/lapack for software. $\endgroup$ – copper.hat Aug 18 '12 at 21:16
  • 1
    $\begingroup$ One tip: don't program it yourself. Use one of the existing libraries. $\endgroup$ – Fabian Aug 18 '12 at 21:29
  • 1
    $\begingroup$ Thanks, but I've been looking around and I can't put the two together: there's methods for finding a single root of a polynomial like Newton-Rhapson, methods for finding all roots of a polynomial like Durand-Kerner, and methods for finding a single root of a system of polynomials. But how do you find all roots of a system? Could you link an example? Thanks $\endgroup$ – Kurt Aug 18 '12 at 22:52
  • $\begingroup$ You've looked into Gröbner bases by any chance? Barring that, see this book for a discussion on using homotopy methods, and this FORTRAN library. $\endgroup$ – J. M. is a poor mathematician Aug 19 '12 at 3:31

A code designed implementing Homotopy Continuation by the name of PHCpack is available with both C and maple interfaces.

I would not suggest trying to implement something like this yourself, since there are many fine points which are easily overlooked, and you may end up getting less solutions than you expected. A nice example of how the method works and the the related problems, can be seen here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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