1
$\begingroup$

Apart from low degree polynomials (2, 3, and 4) and factoring to lowest degrees, what are the method(s) used to find all the roots of a high-degree polynomial equations having only complex roots, and cannot be factored into lower degree polynomials?

In other words, what is the general method Computer Algebra systems (e.g. Maple, Mathematica) use to give you all the roots of polynomials equations?

  • 0
    Aha, ok. I didn't know they write these details in the manuals! I will check them, thanks.2011-04-12

2 Answers 2

2

For Mathematica and for Maple

You should look at this pdf from MIT

In reality, it just like @zhen lin comment.

0

Maybe this is a little bit off topic because it does not handle Maple or Mathematic, but nevertheles it may be useful.

The CAS maxima supplies the function allroots to find numerically roots of polynomials, and the manual says:

For complex polynomials an algorithm by Jenkins and Traub is used (Algorithm 419, Comm. ACM, vol. 15, (1972), p. 97). For real polynomials the algorithm used is due to Jenkins (Algorithm 493, ACM TOMS, vol. 1, (1975), p.178). A description of the Jenkins-Traub-Algorithm can also be foun in Wikipedia.

A method for finding roots of polynomials is published in "Vorlesungen ueber Numerisches Rechnen" by C.Runge and H.Koenig, Berlin 1924 and is called Graeffe's Method, an algorithm that does not need approximations of the roots to start. On pp.168-173 they describe a way to handle complex roots.

Annotation: The description in the book is very clear. The description in Wikipedia may not be sufficient to easily implement the method.