Report Number: CS-TR-68-107
Institution: Stanford University, Department of Computer Science
Title: A three-stage variable-shift iteration for polynomial zeros
and its relation to generalized Rayleigh iteration
Author: Jenkins, M. A.
Author: Traub, Joseph F.
Date: August 1968
Abstract: We introduce a new three-stage process for calculating the
zeros of a polynomial with complex coefficients. The
algorithm is similar in spirit to the two-stage algorithms
studied by Traub in a series of papers. The algorithm is
restriction free, that is, it converges for any distribution
of zeros. A proof of global convergence is given.
Z eros are calculated in roughly increasing order of magnitude
to avoid deflation instability. Shifting is incorporated in a
natural and stable way to break equimodularity and speed
convergence. The three stages use no shift, a fixed shift,
and a variable shift, respectively.
To obtain additional insight we recast the problem and
algorithm into matrix form. The third stage is inverse
iteration with the companion matrix, followed by generalized
A program implementing the algorithm was written in a dialect
of ALGOL 60 and run on Stanford University's IBM 360/67. The
program has been extensively tested and testing is
continuing. For polynomials with complex coefficients and of
degrees ranging from 20 to 50, the time required to calculate
all zeros averages $8n^2$ milliseconds.
Timing information and a numerical example are provided. A
description of the implementation, an analysis of the effects
of finite-precision arithmetic, an ALGOL 60 program, the
results of extensive testing, and a second program which
clusters the zeros and provides a posteriori error bounds
will appear elsewhere.