Evaluating or finding the roots of a polynomial f(z) = f0 + ⋅⋅⋅ + fdzd with floating-point number coefficients is a ubiquitous problem. By using a piecewise approximation of f obtained with a careful use of the Newton polygon of f, we improve state-of-the-art upper bounds on the number of operations to evaluate and find the roots of a polynomial. In particular, if the coefficients of f are given with m significant bits, we provide for the first time an algorithm that finds all the roots of f with a relative condition number lower than 2m, using a number of bit operations quasi-linear in the bit-size of the floating-point representation of f. Notably, our new approach handles efficiently polynomials with coefficients ranging from 2− d to 2d, both in theory and in practice.

The recent advanced sub-division algorithm is nearly optimal for the approximation of the roots of a dense polynomial given in monomial basis; moreover, it works locally and slightly outperforms the user's choice MPSolve when the initial region of interest contains a small number of roots. Its basic and bottleneck block is counting the roots in a given disc on the complex plain based on Pellet's theorem, which requires the coefficients of the polynomial and expensive shift of the variable. We implement a novel method for both root-counting and exclusion test, which is faster, avoids the above requirements, and remains efficient for sparse input polynomials. It relies on approximation of the power sums of the roots lying in the disc rather than on Pellet's theorem. Such approximation was used by Schönhage in 1982 for the different task of deflation of a factor of a polynomial provided that the boundary circle of the disc is sufficiently well isolated from the roots. We implement a faster version of root-counting and exclusion test where we do not verify isolation and significantly improve performance of subdivision algorithms, particularly strongly in the case of sparse inputs. We present our implementation as heuristic and cite some relevant results on its formal support presented elsewhere.