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.
Supplemental Material
Available for Download
Jenkins and Traub: zeros of a complex polynomial Gams: Jenkins and Traub
- 1 Traub, J.F. A class of globally convergent iteration functions for the solution of polynomial equations. Math. Comp. 20 (1966), 113-138.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
Recommendations
Localization of the complex zeros of parametrized families of polynomials
Let P"n(x)=x^m+p"m"-"1(n)x^m^-^1+...+p"1(n)x+p"m(n) be a parametrized family of polynomials of a given degree with complex coefficients p"k(n) depending on a parameter n@?Z">="0. We use Rouche's theorem to obtain approximations to the complex roots of P"...
Mehler formulae for matching polynomials of graphs and independence polynomials of clawfree graphs
The independence polynomial of a graph G is the polynomial @?"Ix^|^I^|, summed over all independent subsets I@?V(G). We show that if G is clawfree, then there exists a Mehler formula for its independence polynomial. This was proved for matching ...
On the zeros of complex Van Vleck polynomials
Polynomial solutions to the generalized Lame equation, the Stieltjes polynomials, and the associated Van Vleck polynomials, have been studied extensively in the case of real number parameters. In the complex case, relatively little is known. Numerical ...
Comments