A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots

Abstract

Given a polynomial $p(z)$ of degree n with m bit integer coefficients and an integer $\mu $, the problem of determining all its roots with error less than $2^{ - \mu } $ is considered. It is shown that this problem is in the class NC if $p(z)$ has all real roots. Some very interesting properties of a Sturm sequence of a polynomial with distinct real roots are proved and used in the design of a fast parallel algorithm for this problem. Using Newton identities and a novel numerical integration scheme for evaluating a contour integral to high precision, this algorithm determines good approximations to the linear factors of $p(z)$.