Polynomial rootfinding

Problem 3.1, polynomial rootfinding. Given a positive b and real or complex coefficients $p_0, \ldots, p_{n-1}$of the monic polynomial $p(x)=\sum_{i=0}^{n}p_ix^i =\prod_{j=1}^n(x-z_j)$with zeros $z_1, \ldots, z_n$lying in the unit disc $D(0,1)=\{x: \vert x\vert \le 1\}$, compute approximations to the zero, $z_1^*, \ldots, z_n^*,$satisfying $$\vert z_j^*-z_j\vert < 2^{-b}, ~j=1, \ldots, n.$$

If some zeros of p(x) are not in the unit disc D(0,1) , we may compute the values $r^*=\max _{k \ge 1} \vert p_{n-k} / p_{n} \vert^{1/k}$, $r^+=1.62r^*$, recall from [He74], pp. 451-457, that $r^+ > {\rm max}_{j} \vert z_j\vert$, and scale the variable x , that is, shift from p(x) to the monic polynomial $q(y)= (r^+)^{-n} p(y r^+)$with zeros $z_j/r^+, j=1, \ldots, n$.

For a few millennea, the study of this problem was crucial for the development of mathematics and applied mathematics; presently this subject remains highly important for computer algebra (cf. [P97], [P98a]). The solution of this algebraic problem typically combines numerical and algebraic techniques, in some cases also involving geometric search on the complex plane. In particular, this is the case for the recent algorithms of [P95] (cf. also [P96], [P97], [P98a]), which support the following results.

THEOREM 3.1   Problem 3.1 can be solved at the computational cost bounded
by $O_A((n \log^2 n) (\log^2 n + \log b))$as well as by $O_A((\log^3 n) (\log^3 n + \log b), n/\log n)$and
$O_B((\log^3 n) \log^2 (bn) , M ((b\log(bn)+n) n^2 ) / ( \log^2 (bn) (\log^2 n)))$, where M(d) is the Boolean complexity of multiplication of a pair of integers modulo $2^d$, $M(d)=O((d \log d) \log \log d)$.

The estimates of Theorem 3.1 are optimal (up to polylogarithmic factors in n and b) under both arithmetic and Boolean models and in both cases under both sequential and parallel models of computing, because they are within polylogarithmic factors from the number of input coefficients as well as from the number of binary bits required to represent these coefficients in order to enable obtaining the output zeros within the error bound $2^{-b}$. Indeed, we need to process all the n coefficients $p_0, \ldots, p_{n-1}$in order to obtain even a single zero $z_j$. Moreover, we have to process order of $bn^2$ bits of n/2 trailing coefficients of such a polynomial as $(x-1/7)^n$in order to approximate within $2^{-b}$ its single (n -multiple) zero $z_1=1/7$.

The algorithms of [P95], [P96] supporting Theorem 3.1 involve sophisticated and advanced algebraic, numerical and geometric techniques, and this slows down the process of their numerical testing and practical implementation. The reader is referred to [P97] on the currents most competitive practical algorithms for polynomial rootfinding.