TOMS429
Localization of the Roots of a Polynomial

TOMS429 is a FORTRAN77 library which implements ACM TOMS algorithm 429, for localization of the roots of a polynomial.

While the text of many ACM TOMS algorithms is available online through ACM: http://www.acm.org/pubs/calgo or NETLIB: http://www.netlib.org/toms/index.html, most of the early algorithms are not available. This is one of them. I typed it in.

This version of the algorithm incorporates corrections and improvements suggested by Driessen and Hunt.

Usage:

call polyan ( c, cm, n )

where C(1:N) contains the polynomial coefficients, omitting the leading coefficient, which is assumed by normalization to be 1, and starting with the coefficient of X^(N-1); CM(1:N) is a work vector and N is the degree of the polynomial.

Languages:

TOMS429 is available in a FORTRAN77 version.

Reference:

1. HB Driessen, EW Hunt,
   Remark on Algorithm 429,
   Communications of the ACM,
   September 1973, Volume 16, Number 9, page 579.
2. Paul Saylor, James Sebastian,
   Algorithm 429: Localization of the Roots of a Polynomial,
   Communications of the ACM,
   Volume 15, Number 8, August 1972, pages 776-777.

Source Code:

• toms429.f, the source code.
• toms429.sh, commands to compile the source code.

Examples and Tests:

• toms429_prb.f, a sample calling program.
• toms429_prb.sh, commands to compile and run the sample program.
• toms429_prb_output.txt, the output from a run of the sample program.

List of Routines:

• POLYAN determines localization information about a polynomial;
• RADIUS bounds the roots inside a ring;
• BOUND returns an upper limit for the positive real roots;
• HRWTZR employs a modification of the Routh-Hurwitz criterion to determine wheterh the polynomial has any roots with positive real parts;

You can go up one level to the FORTRAN77 source codes.