Jenkins-Traub algorithm

The Jenkins-Traub algorithm is an iterative method for finding all the zeros of a polynomial, published in 1970 by Michael A. Jenkins and Joseph F. Traub. It finds the roots one at a time, generally in increasing order of size, and after each root is found it divides off the matching linear factor so that no root is found twice and all roots are found. Each root is located in three stages that correspond to variants of inverse power iteration: a no-shift stage, a fixed-shift stage and a variable-shift stage. Its central idea is to improve the remaining cofactor polynomial step by step rather than only the root itself. The authors gave two variants. The complex-coefficient version, known as CPOLY, was published as ACM Algorithm 419. The real-coefficient version, known as RPOLY, works in real arithmetic by finding either a linear or a quadratic factor, runs about four times faster on the same real polynomial, and is described as practically a standard in black-box polynomial root-finders. The method has faster than quadratic convergence, is connected to the shifted QR algorithm for matrix eigenvalues, and can lose precision through deflation on polynomials whose zeros lie on half-circles of very different radii.