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?

$\endgroup$
14
  • $\begingroup$ Do you mean an exact solution by radicals, or a numerical solution? Mathematica sometimes gives exact roots in a rather unhelpful form, e.g. Root[3 + #1 + #1^5 &, 1]... $\endgroup$
    – Zhen Lin
    Apr 12, 2011 at 10:36
  • $\begingroup$ No, I mean approximate, as exact solutions are not always possible in case the answer is irrational, or -worse- transcendental. $\endgroup$
    – Rafid
    Apr 12, 2011 at 10:39
  • 1
    $\begingroup$ Have you looked at this Wikipedia article? There are many, many algorithms. I have heard that eigenvalue algorithms are the best ones we have available for polynomial equations, but I don't know what Mathematica specifically uses. (It might be in the documentation.) $\endgroup$
    – Zhen Lin
    Apr 12, 2011 at 10:44
  • 1
    $\begingroup$ @Promather, the solution of a polynomial is by definition an algebraic number. $\endgroup$
    – quanta
    Apr 12, 2011 at 10:44
  • 2
    $\begingroup$ @quanta, you are right, only if you suppose the coefficients are integral or rational, which is not necessary: en.wikipedia.org/wiki/Algebraic_number $\endgroup$
    – Rafid
    Apr 12, 2011 at 10:50

2 Answers 2

Reset to default
2
$\begingroup$

For Mathematica and for Maple

You should look at this pdf from MIT

In reality, it just like @zhen lin comment.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .