An Exact Method for Finding the Roots of a Complex Polynomial
James R. Pinkert · ACM Transactions on Mathematical Software · 1976
Let G be a univariate polynomial with rational complex coefficients.A new SAC-1 module is described which uses algebraic algorithms based on the classical theorems of Sturm and Routh to isolate the unique roots of G into disjoint squares m the complex plane.These squares can then be refined to any prespecified rational width.Furthermore, the algorithms can associate with each square the multiplicity of the unique root of G contained in that square.Exact arithmetic is used so that all computational errors are eliminated.The system is self-sufficient in the sense that no starting approximations are needed, and no user interaction during computation is required.The methods used ensure termination of the algorithms with the desired squares regardless of such aspects as multiple roots, roots which are distinct but very close together, or polynomials with high condition numbers.Theoretical computing times are analyzed and compared to empirical results.