Root refinement for real polynomials using quadratic interval refinement

We consider the problem of approximating all real roots of a square-free polynomial ff with real coefficients. Given isolating intervals for the real roots and an arbitrary positive integer LL, the task is to approximate each root to LL bits after the binary point. Abbott has proposed the quadratic interval refinement method (QIR for short), which is a variant of Regula Falsi combining the secant method and bisection. We formulate a variant of QIR, denoted AQIR (“Approximate QIR”), that considers only approximations of the polynomial coefficients and chooses a suitable working precision adaptively. It returns a certified result for any given real polynomial, whose roots are all simple. In addition, we propose several techniques to improve the asymptotic complexity of QIR: We prove a bound on the bit complexity of our algorithm in terms of the degree of the polynomial, the size and the separation of the roots, that is, parameters exclusively related to the geometric location of the roots. For integer coefficients, our variant improves, in theory and practice, the variant with exact integer arithmetic. Combining our approach with multipoint evaluation, we obtain near-optimal bounds that essentially match the best known theoretical bounds on root approximation as obtained by very sophisticated algorithms.