Finding all roots of a polynomial Is it possible, for an arbitrary polynomial in one variable with integer coefficients, to determine the roots of the polynomial in the Complex Field to arbitrary accuracy? When I was looking into this, I found some papers on homotopy continuation that seem to solve this problem (for the Real solutions at least), is that correct? Or are there restrictions on whether homotopy continuation will work? Does the solution region need to be bounded?
 A: The wikipedia article http://en.wikipedia.org/wiki/Root-finding_algorithm gives links to many different methods for finding roots of polynomials. (Start at the section entitled "Finding roots of polynomials".) Many of the methods are incomparable, in the sense that they work faster or slower than others depending on the specific polynomial. 
A: Homotopy continuation method is good for finding all COMPLEX solutions to arbitrary accuracy, and it is implemented in the Numerical Algebraic Geometry package in Macaulay 2, for example.  The method is more general.  It can solve a system of polynomial equations in many variables.  In fact, it is a more difficult problem to find all REAL solutions WITHOUT finding all complex solutions.
From what I understand, the solution region does not need to be bounded for homotopy continuation to work.  You can also "projectify" your problem if necessary, so that you don't have to worry about homotopy paths going off to infinity.  Some methods assume that the solutions are all simple, but there're ways to work around it.  One is the method of "deflation".
A: For univariate polynomials you should look at "An Efficient Algorithm for the Complex Roots Problem" by Andy Neff and John Reif http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=5E9156BAF80D8D6AEDCA2F42C11AB4B2?doi=10.1.1.33.3353&rep=rep1&type=pdf
A: I give a course on matrix analysis, and I like to mention the following thing. It is equivalent to finding the roots of polynomials, or to finding the eigenvalues of matrices, because to a polynomial $P$, you can associate its companion matrix $C_P$, and to a square matrix $M$, you can associate its characteristic polynomial $\chi_M$.
Now, because the calculation of $\chi_M$ is costly, and direct solving methods are ill-conditionned, it is usually a bad idea to use polynomial solving in order to compute eigenvalues.
Instead, the efficient idea is to apply the QR method to the companion matrix $C_P$ when you want to calculate the roots of $P$. This way has several advantages:


*

*the method does converge. Proven.

*it is fast. Actually, each iteration produces a Hessenberg matrix (only one non-zero sub-diagonal) and this ensures that the cost of an iteration is only $O(n^2)$, instead of $O(n^3)$.

*it is stable. Because an iteration acts as a unitary conjugation. Therefore the round-off errors only add up, but are not amplified.


I agree that because of the round-off errors, this produces on a computer approximations of limited (but outstanding) precision. What you can do is to stop after a few hundred iterations, and then apply Newton's method or something similar, starting from one of the approximate eigenevalues.
A: One of the semi-recommended ones for finding roots in the complex plane is Laguerre's method, which for some reason is not included in the Wikipedia article on root-finding. 
http://en.wikipedia.org/wiki/Laguerre's_method 
The reason I know of this is a colloquium lecture long ago by Steven Smale on the complexity of Newton's method, during which William Kahan stood up and held forth on why Newton's method was worthless and Laguerre's was much better.
I cannot tell whether you insist on finding all roots to high accuracy. One could perhaps divide out by $(x - r_k)^{n_k}$ each time a root $r_k$ with multiplicity $n_k$ is found, and search for roots for the new polynomial, using those results as seed values for finding accurate roots using the original polynomial.
A: This can be done.  Check this article by Hubbard, Schleicher, and Sutherland, entitled "How to find all roots of complex polynomials by Newton's method".
A: You have already seen McNamee's excellent bibliography on polynomial root-finding methods?
Personally I have a preference for the "simultaneous iteration" methods (of which Durand-Kerner and Ehrich-Aberth are two of the simplest and most well-known); all you need to start from is a set of points equispaced around a circle in the complex plane (as to the radius of this circle, there are a number of suggestions in the literature; alternatively, formulas in Marden's "Geometry of Polynomials" might be of use here).
A: At least for real roots it can be completely solved by bracketing zeroes with Sturm sequences.
A: This argument is problematic; see Andrej Bauer's comment below.

Sure.  I have no idea what an efficient algorithm looks like, but since you only asked whether it's possible I'll offer a terrible one.  
Lemma:  Let $f(z) = z^n + a_{n-1} z^{n-1} + \cdots + a_0$ be a complex polynomial and let $R = \max(1, |a_{n-1}| + \cdots + |a_0|)$.  Then all the roots of $f$ lie in the circle of radius $R$ centered at the origin.
Proof.  If $|z| > R$, then $|z|^n > R |z|^{n-1} \ge |a_{n-1} z^{n-1}| + \cdots + |a_0|$, so by the triangle inequality no such $z$ is a root.
Now subdivide the disk of radius $R$ into, say, a mesh of squares of side length $\varepsilon > 0$ and evaluate the polynomial at all the lattice points of the mesh.  As the mesh size tends to zero you'll find points that approximate the zeroes to arbitrary accuracy.
There are also lots of specialized algorithms for finding roots of polynomials at the Wikipedia article.
A: Although it's not specific to polynomials with integer coefficients, have a look at "Computing the Zeros of Analytic Functions".
A: A completely ineffective theoretical method goes as follows: Write $f(z)$ as $f_r(x,y)+if_i(x,y)$
where $f_r,f_i\in \mathbb R[x,y]$ are real polynomials in the real and complex part 
$x,y$ of $z=x+i y$.
Compute a Groebner basis of the ideal $(f_r,f_i)$ with respect to an order
which eliminates one of the variables in the first element of the basis and use
real techniques (based on Sturm sequences) to compute, say, the real parts of all solutions.
Use another element of the Groebner basis (or again real techniques) to compute the corresponding imaginary part and test for multiplicities (which can be avoided by computing first gcd$(f,f')$).
Completely useless (and equivalent) variation: Study the intersection giving the zeroes of $f$
of the two real curves determined by $f_r$ and by $f_i$.
A: Back in the days before elecronic computers, methods were known for this.  I read about them in the nice book,
J. V. Uspensky, Theory of Equations (1948 ... 1963)  
Look for:
Chapter VIII, "Approximate Evaluation of Roots"  (real roots)
Appendix V, "Graeffe's Method" (complex roots)  
All computations are done by hand, and you find as many places as you wish for the roots.
