Near-optimal Algorithms for Computing Real Roots of a Polynomial

In the first part of my talk, I will present a variant of the Descartes method, denoted ANEWDSC, that computes isolating intervals for the real roots of any real square-free polynomial, given by an oracle that provides arbitrary good approximations of the polynomial's coefficients. The algorithm can also be used to refine the isolating intervals to an arbitrary small size. The bit complexity of ANEWDSC matches the complexity of Pan's method and, in particular, it achieves near optimal complexity for computing arbitrary good approximations of all real roots. ANEWDSC derives its speed from the combination of the Descartes method with Newton iteration and approximate arithmetic. By comparison, the algorithm is considerably simpler than Pan's method, and it can be used to compute the roots in a given interval only.

In the second part of my talk, I will concentrate on sparse polynomials, that is, polynomials with a small number of non-vanishing coefficients. Using a subroutine from ANEWDSC, I will show how to isolate the real roots of a sparse integer polynomial with a number of arithmetic operations over the rationals that is polynomial in the input size of the sparse representation of the input polynomial. The bit complexity of the algorithm is by one magnitude better than that of ANEWDSC and Pan's method. Considering a family of Mignotte-like polynomials, one can show that the algorithm is optimal up to logarithmic factors in the degree of the polynomial and the bitsize of the coefficients.