New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems

We present a new data structure to approximate accurately and efficiently a polynomial
$f$
of degree
$d$
given as a list of coefficients f
i
. Its properties allow us to improve the state-of-the-art bounds on the bit complexity for the problems of root isolation and approximate multi-point evaluation. This data structure also leads to a new geometric criterion to detect ill-conditioned polynomials, implying notably that the standard condition number of the zeros of a polynomial is at least exponential in the number of roots of modulus less than 1/2 or greater than 2. Given a polynomial
$f$
of degree
$d$
with ║f║
1
= Σ | f
i
| ≤ 2
^τ
for τ ≥ 1, isolating all its complex roots or evaluating it at
$d$
points can be done with a quasi-linear number of arithmetic operations. However, considering the bit complexity, the state-of-the-art algorithms require at least d
^3/2
bit operations even for well-conditioned polynomials and when the accuracy required is low. Given a positive integer
$m$
, we can compute our new data structure and evaluate
$f$
at
$d$
points in the unit disk with an absolute error less than 2
^−m
in Õ(d(τ + m)) bit operations, where Õ(.) means that we omit logarithmic factors. We also show that if κ is the absolute condition number of the zeros of f, then we can isolate all the roots of
$f$
in Õ(d(τ + log κ)) bit operations. Moreover, our algorithms are simple to implement. For approximating the complex roots of a polynomial, we implemented a small prototype in Python/NumPy that is an order of magnitude faster than the state-of-the-art solver MPSolve for high degree polynomials with random coefficients.