Algorithm 419: zeros of a complex polynomial [C2]

ABSTRACT

The subroutine CPOLY is a Fortran program to find all the zeros of a complex polynomial by the three-stage complex algorithm described in Jenkins and Traub [4]. (An algorithm for real polynomials is given in [5].) The algorithm is similar in spirit to the two-stage algorithms studied by Traub [1, 2]. The program finds the zeros one at a time in roughly increasing order of modulus and deflates the polynomial to one of lower degree. The program is extremely fast and the timing is quite insensitive to the distribution of zeros. Extensive testing of an Algol version of the program, reported in Jenkins [3], has shown the program to be very reliable.

REFERENCES

• 1: Traub, J.F. A class of globally convergent iteration functions for the solution of polynomial equations. Math. Comp. 20 (1966), 113-138.
• 2: Traub, J.F. The calculation of zeros of polynomials and analytic functions. In Mathematical Aspects of Computer Science, Proceedings Symposium Applied Mathematics, Fol. 19, Amer. Math. Soc., Providence, R.I., 1967, pp. 138-152.
• 3: Jenkins, M.A. Three-stage variable-shift iterations for the solution of polynomial equations with a posteriori error bounds for the zeros. Diss., Rep. CS 138, Comput. Sci. Dep., Stanford U., Stanford, Cal., 1969.
• 4: Jenkins, M.A., and Traub, J.F. A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration. Numer. Math. 14 (1970), 252-263.
• 5: Jenkins, M.A., and Traub, J.F. A three-stage algorithm for real polynomials using quadratic iteration. SlAM J. Numer. Anal. 7 (1970), 545-566.

INDEX TERMS

Keywords:
roots, roots of a polynomial, zeros of a polynomial