OPTIMAL AND NEARLY OPTIMAL-ALGORITHMS FOR APPROXIMATING POLYNOMIAL ZEROS

We substantially improve the known algorithms for approximating all th e complex zeros of an n(th) degree polynomial p(x). Our new algorithms save both Boolean and arithmetic sequential time, versus the previous best algorithms of Schonhage [1], Pan [2], and Neff and Pelf [3]. In parallel (NC) implementation, we dramatically decrease the number of p rocessors, versus the parallel algorithm of Neff [4], which was the on ly NC algorithm known for this problem so far. Specifically, under the simple normalization assumption that the variable a: has been scaled so as to confine the zeros of p(x) to the unit disc {x : \x\ less than or equal to 1}, our algorithms (which promise to be practically effec tive) approximate all the zeros of p(a) within the absolute error boun d 2(-b), by using order of n arithmetic operations and order of (b + n )n(2) Boolean (bitwise) operations (in both cases up to within polylog arithmic factors). The algorithms allow their optimal (work preserving ) NC parallelization, so that they can be implemented by using polylog arithmic time and the orders of n arithmetic processors or (b + n)n(2) Boolean processors. All the cited bounds on the computational complex ity are within polylogarithmic factors from the optimum (in terms of n and b) under both arithmetic and Boolean models of computation (in th e Boolean case, under the additional (realistic) assumption that n = O (b)).