---
res:
bibo_abstract:
- 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Michael
foaf_name: Kerber, Michael
foaf_surname: Kerber
foaf_workInfoHomepage: http://www.librecat.org/personId=36E4574A-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-8030-9299
- foaf_Person:
foaf_givenName: Michael
foaf_name: Sagraloff, Michael
foaf_surname: Sagraloff
bibo_doi: 10.1145/1993886.1993920
dct_date: 2011^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Root refinement for real polynomials@
...