2
$\begingroup$

Given an nth order polynomial, is there any algorithm that can calculate all the roots ? Is there any algorithm that can calculate ALL the roots of the equation ?

$$p(x)=p_nx^n+p_{n-1}x^{n-1}+\cdots+p_1x+p_0$$

All coefficients are real, and I'm only looking for real roots.

$\endgroup$
  • $\begingroup$ Are you looking for a numerical algorithm for approximate solutions or an algebraic algorithm for "closed form" solutions? $\endgroup$ – Joonas Ilmavirta Dec 16 '14 at 8:52
  • $\begingroup$ Mark McClure's answer here deserves some more upvotes. He beautifully summarizes a recent paper, "How to find all roots of complex polynomials by Newton's method", by Hubbard, Schliecher, and Sutherland, that does just what you want: "Not only is there a method but, due to the stability of the fixed points under iteration of the Newton's method function, there is a very good method." $\endgroup$ – MJD Dec 16 '14 at 9:00
  • $\begingroup$ @JoonasIlmavirta Approximations are just fine. $\endgroup$ – kiranmathewkoshy Dec 16 '14 at 9:15
  • $\begingroup$ @MJD From what I managed to understand, it does not give any assurance that the roots can be found in linear time. If any two of the roots are too close, I think it would take a long time to finish selecting the seeds $\endgroup$ – kiranmathewkoshy Dec 16 '14 at 9:24
  • $\begingroup$ I believe you are mistaken. See the section on page 5 that begins "concerning the number of iterations...". $\endgroup$ – MJD Dec 16 '14 at 9:28

Your Answer

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

Browse other questions tagged or ask your own question.