New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems
Guillaume Moroz · 2022
We present a new data structure to approximate accurately and efficiently a polynomial$f$of degree$d$given as a list of coefficients fi. 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= Σ | fi| ≤ 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 d3/2bit 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−min Õ(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.