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
    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]`...2011-04-12
  • 0
    No, I mean approximate, as exact solutions are not always possible in case the answer is irrational, or -worse- transcendental.2011-04-12
  • 1
    Have you looked at [this Wikipedia article](http://en.wikipedia.org/wiki/Root-finding_algorithm)? 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.)2011-04-12
  • 1
    @Promather, the solution of a polynomial is *by definition* an algebraic number.2011-04-12
  • 0
    @Zhen, yes, I definitely looked at it, but first, it is about solving polynomial with real solutions, and when it comes to complex solutions, the problem becomes very complicated. Second, when I tried these algorithms, I always ran into problems of approximation, finding initial guess, etc. This is why I added "in Computer Algebra Systems" to the subject. That is, I want to know how Computer Algebra systems solve polynomial equations of all kinds.2011-04-12
  • 2
    @quanta, you are right, only if you suppose the coefficients are integral or rational, which is not necessary: http://en.wikipedia.org/wiki/Algebraic_number2011-04-12
  • 0
    @quanta, for example the polynomial pi*x - 1 = 0, has the solution x = 1/pi, which is clearly transcendental.2011-04-12
  • 0
    @Promather: If I remember correctly you can get bounds on the roots of a polynomial in terms of its coefficients using e.g. the principle of the argument.2011-04-12
  • 0
    *Mathematica* uses Jenkins-Traub (which can be considered as a Rayleigh quotient iteration applied to a Frobenius companion matrix, or as a modernized Bernoulli method). MATLAB applies the QR algorithm for eigenvalues on the Frobenius companion matrix. As for other methods, you should give [McNamee's book](http://books.google.com/books?id=4PMqxwG-eqQC) a look.2011-04-12
  • 0
    @Zhen: I agree the numbering of *Mathematica*'s `Root[]` function is sort of screwy, but I consider it sometimes helpful being told of the minimal polynomial for the root in question (which is what the first argument of `Root[]` is).2011-04-12
  • 0
    @J.M., thanks. First, why don't you post your comment as an answer?! :-) Second, can you provide a reference?2011-04-12
  • 0
    @Zhen, not sure I understand your last comment!2011-04-12
  • 0
    Reference for which? The manuals for those computing environments clearly state what algorithms they used. I'll post an answer if I could write up something detailed (and my comment as it stands isn't), which I do not currently have time for.2011-04-12
  • 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