On the Complexity of Polynomial Zeros
Dario A. Bini, Luca Gemignani · SIAM Journal on Computing · 1992
The parallel complexity of the simultaneous approximation to all the zeros of a polynomial is investigated. By modifying and analyzing an algorithm given by Householder, it is possible to obtain a priori bounds to the number of iterations sufficient to yield a given accuracy, and to the number of digits required in the finite arithmetic. More classes of polynomials, for which the simultaneous approximation to all the zeros can be carried out in polylogarithmic time, are found. Some cases of polynomials, customarily considered hard, are easily solved. The root-finding problem for a polynomial of degree n, having zeros $z_i $, $i = 1, \cdots ,n$ is $\mathcal{NC}$-reduced to finding a polynomial $a(z)$ such that $|a(z_i + 1)/a(z_i )| \leq 1 - 1/n^c $, where c is a constant.