Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a large univariate polynomial, say of degree 200 or more, is there a procedural way of finding all the complex roots? By "roots", I mean complex decimal approximations to the roots, though the multiplicity of the root is important. I have access to MAPLE and the closest function I've seen is:

with(RootFinding):
Analytic(Z,x,-(2+2*I)..2+2*I);

but this chokes if Z is of high degree (in fact it fails to complete even if deg(Z)>15).

share|improve this question
    
What do you mean by fails to complete? –  Mariano Suárez-Alvarez Oct 22 '10 at 20:08
    
Fails to complete -> fails return any solutions in a reasonable time (by which I arbitrary define to be > 1 hour for a 15th degree polynomial). I thought that numerically such a problem on a modern computer should have been easier, but perhaps I'm missing something. –  Hooked Oct 22 '10 at 20:32
    
Have you read en.wikipedia.org/wiki/…;? –  Hans Lundmark Oct 22 '10 at 20:42
1  
If you want a rough visual indication of where the zeros are, you can make a color plot of the function. I made a webpage with some images some years ago: mai.liu.se/~halun/complex/domain_coloring-unicode.html. For example, a polynomial of degree $2^20$ is here: mai.liu.se/~halun/complex/pics/iterate2_big.png. –  Hans Lundmark Oct 22 '10 at 20:55
    
@ Lundmark - I did, and had read through several of the articles before posting. Some of them seemed to have restrictions (diagonally dominant, real roots only, etc...) and figured that the answers coming from this question might provide more insight, especially if the poster had previous experience with one of them. Case-in-point, Rouche's theorem posted by Chandru1 below is not even mentioned on that wikipage! –  Hooked Oct 22 '10 at 21:00

4 Answers 4

up vote 5 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
1  
dx.doi.org/10.1016/0024-3795(93)00341-V is the paper being referred to. This approach, which can be also thought of as the construction of a Sturm sequence from the polynomial and its derivative to form the tridiagonal matrix whose characteristic polynomial is the original polynomial, works especially well for polynomials with real roots in my experience, though it seems to be a mixed bag for polynomials with complex roots. –  J. M. Oct 23 '10 at 11:16

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.

share|improve this answer
    
What a wonderful theorem! It does however seem awkward for "zooming in" to find the zeros. I tried searching around but to no avail, is there a numerical method that uses Rouche's theorem? –  Hooked Oct 22 '10 at 20:42
    
As a matter of fact, there is the so-called "Lehmer-Schur algorithm" for an (intelligent) brute-force search of the complex plane for polynomial roots. The method essentially covers the plane in circles and attempts to count the number of zeroes within a circle. This process is repeated with circles of ever-decreasing radius until all the zeroes are enclosed. As can be expected with an approach, it is accurate but quite slow. –  J. M. Oct 23 '10 at 3:02
    
A minor remark: Lehmer–Schur is (according to Wikipedia) based on the argument principle rather than Rouché's theorem. (But of course these two theorems are closely related.) en.wikipedia.org/wiki/Lehmer%E2%80%93Schur_algorithm –  Hans Lundmark Oct 23 '10 at 7:22
    
Well to be even more precise, it's based on the classical Schur-Cohn test for checking if the roots of a polynomial are within the unit disk, familiar to people in signal processing and digital filter design. By judicious scaling and shifting, the test can be used to see if there are roots of a polynomial within a circle of preset radius and center. –  J. M. Oct 23 '10 at 7:50
    
Here is a method due to Bini that uses the Rouché theorem in tandem with the Ehrlich-Aberth method (another member of the family of "simultaneous iteration" methods I mentioned in my answer) for polynomial rootfinding. –  J. M. Oct 23 '10 at 9:30

I think the following page summarizes the root-finding well, by showing how to reduce it to an appropriate Eigenvalue computation:

http://mathworld.wolfram.com/PolynomialRoots.html

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.