Skip to Main content Skip to Navigation
Journal articles

Nearly Optimal Refinement of Real Roots of a Univariate Polynomial

Abstract : We assume that a real square-free polynomial $A$ has a degree $d$, a maximum coefficient bitsize $\tau$ and a real root lying in an isolating interval and having no nonreal roots nearby (we quantify this assumption). Then we combine the {\em Double Exponential Sieve} algorithm (also called the {\em Bisection of the Exponents}), the bisection, and Newton iteration to decrease the width of this inclusion interval by a factor of $t=2^{-L}$. The algorithm has Boolean complexity $O_B~(d^2 \tau + d L )$. This substantially decreases the known bound $O_B~(d^3 +d^2L)$ and is optimal up to a polylogarithmic factor. Furthermore we readily extend our algorithm to support the same upper bound on the complexity of the refinement of $r$ real roots, for any $r\le d$, by incorporating the known efficient algorithms for multipoint polynomial evaluation. The main ingredient for the latter is an efficient algorithm for (approximate) polynomial division; we present a variation based on structured matrix computation with quasi-optimal Boolean complexity.
Document type :
Journal articles
Complete list of metadatas

Cited literature [55 references]  Display  Hide  Download
Contributor : Elias Tsigaridas <>
Submitted on : Monday, December 28, 2015 - 11:04:21 PM
Last modification on : Tuesday, August 13, 2019 - 1:42:01 PM
Long-term archiving on: : Saturday, April 29, 2017 - 11:55:24 AM


Files produced by the author(s)



Victor Y. Pan, Elias Tsigaridas. Nearly Optimal Refinement of Real Roots of a Univariate Polynomial. Journal of Symbolic Computation, Elsevier, 2015, 74, pp.181-204. ⟨10.1016/j.jsc.2015.06.009⟩. ⟨hal-00960896v2⟩



Record views


Files downloads