An algebraic algorithm to isolate complex polynomial zeros using sturm sequences

In this paper, algorithms to enumerate and isolate complex polynomial roots are developed, analyzed,and implemented. We modified an algorithm due to W ilf, in which Sturm sequences and the principle of argument are used, by em ploying algebraic methods, aiming to enumerate zeros inside a rectangle in an exact way. Several improvements are introduced, such as dealing with zer os on the boundary of the rectangle. The performance of this new algorithm is evaluated in a theoretical as well as from a practical point of view, by means of experimental tests. The robustness of the algorithm is verified b y using tests with ill-conditioned polynomials. We also compare the perform ance of this algorithm with the results of a recent paper, using different polynomial classes. (C) 2000 Elsevier Science Ltd. All rights reserved.