Complex-coefficient polynomial root finding in Java

Question

I'm trying to find a way to compute roots of a polynomial with complex coefficients in Java (i.e. an equivalent of what is ridiculously easily done with roots() in MATLAB).

I'm ready to recode a root finding algorithm that builds the companion matrix and then uses generalized eigenvalue decomposition to find the roots, but for this I would need a library that handles complex-valued matrix operations.

I browsed for a while and nothing convincing seems to be available out there, which I think is rather weird. Then, I'd like to ask you:

1. Do you know a (stable) Java library that performs root finding on polynomials defined by COMPLEX coefficients?

2. Do you know a (stable) Java library that performs evd, svd, inverse, etc. on COMPLEX-valued matrices?

Note: I already looked at JAMA (doesn't handle complex), Michael Thomas Flanagan's Java Scientific Library (not available anymore), colt (doesn't seem to handle complex), Efficient Java Matrix Library (no complex either), DDogleg Numerics (does not handle polynomial with complex coefficients), JScience (not clear if evd is available) and common-math from Apache (not clear if they allow for complex matrices, and if yes, if evd is available).

Diffidence

Answer 1

The Durand-Kerner method also works for complex coefficients and does not rely on matrix computations.

It's quite simple to implement, you could google up an implementation (Stackoverflow forbids me to link the one I found) or make one of your own. You could use the jscience library for the complex data types, not for the algorithm itself.

EDIT: Didn't see that you need evd too, never mind my mention of jscience as an option to do the complex matrix math.

Leifleifer

Thanks a lot! This method was indeed quite easy to implement, and I'm getting good results like that - problem solved. – Diffidence

Answer 2

If one wants to keep it real, use the Bairstow method. If the polynomial has odd degree, use first Newton's method to find a real root and reduce the polynomial to even degree. This avoids an odd singularity of the Bairstow method where it converges towards a quadratic polynomial that has infinity as one root. Information of good quality can be found at the usual places. Some of it written or edited by yours truly.

Determine an inner root radius r and use z^2-2r*cos(phi)*z+r^2 with random angle phi as initial factor for Bairstow's method. It produces in each step a quadratic factor, always in and with real coefficients, containing either a pair of real roots or a conjugate pair of complex roots.

Check in each step for speed of convergence and restart with a different initial point if necessary. Find new roots after deflation, and polish the roots or quadratic factors by executing the method with the original polynomial and the factors as starting point.

Abjuration