In circuit and control systems theory, a need for determining the complex roots of polynomials frequently arises. In fact, whenever Laplace transforms are tools of choice for solving systems governed by differential equations, polynomials will occur. In these applications the roots are generally complex, so there is a common need for a solver which finds all roots, real and complex.
This page provides links to several files which will do the job. You will find software based on Bairstow's method, which uses a Newton-type iteration on quadratic factors, and a full port of the famous Jenkins-Traub method from FORTRAN to C++. A simple driver for the Jenkins-Traub port is available at rptst.cpp.
For those situations which require polynomial roots beyond double precision accuracy, the Jenkins-Traub method has been ported to the XBCD extended precision math package. A command line executable using extended precision can be found here.
Here you will find C++ source code and a DOS executable implementing a new method for finding polynomial roots. A paper describing the method in detail is also available. The method was developed to solve convergence problems associated with iterative methods for finding roots when the multiplicity of one or more roots is greater than unity. It uses recursive differentiation to reduce the order of multiple roots to unity so that the root location can be found to machine accuracy.
This method has also been implemented in XBCD extended precision format. Polynomial root finding is one of the areas of applied math where extended precision is often required. The program: xbbpr.exe is available here as a (*.zip) file.
The method described in the previous section uses recursive differentiation to isolate multiple roots for extraction at machine precision. It has been found to be very successful at recovering roots of polynomials which defeat conventional solvers. The solution strategy described in this paper uses Euclid's algorithm to identify and divide out multiple roots so that the solver never has to deal with them at all. The process is stable and has been implemented in a preprocessor (front end) which works with an iterative solver to find all real and complex roots of real polynomials.
The use of Euclid's algorithm to determine the greatest common divisor (GCD) of a polynomial, sometimes called the greatest common factor (GCF), in connection with the multiple root problem has been suggested before amid mixed reviews. Nevertheless, the author has found that superior performance is possible compared with purely iterative root finding strategies.
The front end also includes a root estimator which uses a novel formulation of Rutishauser's Quotient-Difference algorithm to globally estimate all roots simultaneously. The combination considerably eases the burden on iterative solvers and could be used with any of the methods in common use, such as Newton's, Mullers, Bairstow's, etc. Below you will find a group of miscellaneous polynomials with their roots as found by an implementation of this method.
