Newton's Method for Finding Multiple Roots  Is it feasible to use Newton's method to find all the roots (if more than one) of a polynomial? Are there any efficient algorithms for finding all the roots? 
 A: The Newton's method has driven a lot of attention during the past decades in the community of complex analysis, because of its nice behaviour as a dynamical system. From the point of view of the approximation of the roots of a polynomial $P$, it has contrasted properties. On the one hand, it is a fast method for calculating one root $a$. But once you have a good approximation $\alpha$ of it, you face the problem of dividing $P$ by $X-\alpha$. This division is not exact, and it is unstable if $P$ has an other root close to $a$. The latter case happens frequently in large matrices, either random or with physical meaning.
This is why the codes employed by computers to calculate the set of roots follows an other idea. Form the companion matrix $B_P$, which turns out to be of Hessenberg form ($b_{ij}=0$ if $i\ge j+2$). Then apply the QR method. This one enjoys crucial properties:


*

*it preserves the Hessenberg form,

*one iteration is fast when applied to a Hessenberg matrix ($O(n^2)$ operations),

*it is stable, in the sense that the roundoff errors are not amplified along the iterations. This is because one conjugates by unitary matrices.


Naively, we could think that the calculation of eigenvalues of a matrix must be done in two steps, first calculate the characteristic polynomial, then solve it. But the QR method is so much efficient that the converse is actually true: to find the roots of a polynomial, form the companion matrix and then apply QR.
If you fear that $P$ has multiple roots, you had better to eliminate them first by calculating the g.c.d. of $P$ and $P'$. This is not easy in general, but if $P\in\mathbb Z[X]$, you do it exactly.
Later. I realize that you seem to be interested only on polynomials whose roots are real. If this is correct, then you can accelerate the calculation by the following trick. First form a Sturm sequence of polynomials $P_0=P,P_1=P',\ldots$. Then use it to form a tridiagonal symmetric matrix $H$ whose characteristic polynomial is $P$: $P_{n-j}$ is the characteristic polynomial of the principal $j\times j$ matrix. Now apply QR to $H$. This is really fast. Each iteration requires only $O(n)$ operation, and the method becomes of cubic order.
A: Yes: see e.g. MR1859017 (2002i:37059) Reviewed 
Hubbard, John(1-CRNL); Schleicher, Dierk(D-MNCH-MI); Sutherland, Scott(1-SUNYS-IM)
How to find all roots of complex polynomials by Newton's method. (English summary) 
Invent. Math. 146 (2001), no. 1, 1–33. 
A: Another good choice is the Aberth method http://en.wikipedia.org/wiki/Aberth_method. It has  some advantages wrt the QR-based approaches, especially when the coefficients have very different magnitudes.
A: Use Sturm sequences. Or form a matrix that has eigenvalues equal to the roots of your polynomial and apply the QR iteration.
A: There is another method based on circles on the complex plane named splitting circle method http://en.wikipedia.org/wiki/Splitting_circle_method. 
