Root refinement for real polynomials Kerber, Michael ; https://orcid.org/0000-0002-8030-9299 Sagraloff, Michael We consider the problem of approximating all real roots of a square-free polynomial f. Given isolating intervals, our algorithm refines each of them to a width at most 2-L, that is, each of the roots is approximated to L bits after the binary point. Our method provides a certified answer for arbitrary real polynomials, only requiring finite approximations of the polynomial coefficient and choosing a suitable working precision adaptively. In this way, we get a correct algorithm that is simple to implement and practically efficient. Our algorithm uses the quadratic interval refinement method; we adapt that method to be able to cope with inaccuracies when evaluating f, without sacrificing its quadratic convergence behavior. We prove a bound on the bit complexity of our algorithm in terms of degree, coefficient size and discriminant. Our bound improves previous work on integer polynomials by a factor of deg f and essentially matches best known theoretical bounds on root approximation which are obtained by very sophisticated algorithms. Springer 2011 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject conferenceObject http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/3330 Kerber M, Sagraloff M. Root refinement for real polynomials. In: Springer; 2011:209-216. doi:<a href="https://doi.org/10.1145/1993886.1993920">10.1145/1993886.1993920</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1145/1993886.1993920 info:eu-repo/semantics/altIdentifier/arxiv/1104.1362 info:eu-repo/semantics/openAccess