Finding all complex zeros of a high-degree polynomial

Solution 1:

Everyone's first starting point when dealing with the polynomial rootfinding problem should be a peer at J.M. McNamee's excellent bibliography and book.

Now, it is a fact that polynomials of very high degree tend to make most polynomial rootfinders choke. Even the standard blackbox, the Jenkins-Traub algorithm, can choke if not properly safeguarded. Eigenmethods, while they can have nice accuracy, can be very demanding of space and time (O(n²) space and O(n³) operations for a problem with only O(n) inputs!)

My point is that unless you are prepared to devote some time and extra precision, this is an insoluble problem.

Having been pessimistic in those last few sentences, one family of methods you might wish to peer at (and I have had personal success with) are the so-called "simultaneous iteration" methods. The simplest of them, (Weierstrass-)Durand-Kerner, is essentially an application of Newton's method to the Vieta formulae, treated as n equations in n unknowns (the assumption taken by (W)DK is that your polynomial is monic, but that is easily arranged).

If you wish for more details and references, the book by McNamee I mentioned earlier is a good start.

Solution 2:

I think one of the biggest problems is approximating multiple roots. The approach described in

L.Brugnano, D.Trigiante. "Polynomial Roots: the Ultimate Answer?", Linear Algebra and its Applications 225 (1995) 207-219

relies on the approximation of eigenvalues of a tridiagonal matrix, obtained via the application of Euclid's GCD algorithm to the original polynomial, and seems to work pretty well.

I couldn't find the pdf for the article though, sorry.

Solution 3:

I think this might help.

Rouche's Theorem: Let $D$ be a bounded domain, with piecewise smooth boundary, $\partial{D}$. Let $f(z)$ and $h(z)$ be analytic on $D \cup \partial{D}$. If $|h(z)| < |f(z)$ for $z \in \partial{D}$, then $f(z)$ and $f(z)+h(z)$ have the same number of zero's in $D$, counting multiplicities.

Example: We find the zeros of the function $p(z)=z^{6}+9z^{4}+z^{3}+2z+4$, inside the unit circle.

For using Rouche's theorem, let $p(z)= f(z) + h(z)$, where $f(z)$ dominates, $h(z)$ inside the unit circle.

Consider $f(z) = 9z^{4}$, which has four zeros inside the unit circle, all at the origin. $h(z) =z^{6}+z^{3}+2z+4$, which satisfies, $|h(z)| < |f(z)|$ for $|z|=1$. Therefore by Rouche's theorem $p(z)$ also has 4 zeros inside the unit circle.