---
_id: '3330'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Michael
  full_name: Kerber, Michael
  id: 36E4574A-F248-11E8-B48F-1D18A9856A87
  last_name: Kerber
  orcid: 0000-0002-8030-9299
- first_name: Michael
  full_name: Sagraloff, Michael
  last_name: Sagraloff
citation:
  ama: '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>'
  apa: 'Kerber, M., &#38; Sagraloff, M. (2011). Root refinement for real polynomials
    (pp. 209–216). Presented at the ISSAC: International Symposium on Symbolic and
    Algebraic Computation, California, USA: Springer. <a href="https://doi.org/10.1145/1993886.1993920">https://doi.org/10.1145/1993886.1993920</a>'
  chicago: Kerber, Michael, and Michael Sagraloff. “Root Refinement for Real Polynomials,”
    209–16. Springer, 2011. <a href="https://doi.org/10.1145/1993886.1993920">https://doi.org/10.1145/1993886.1993920</a>.
  ieee: 'M. Kerber and M. Sagraloff, “Root refinement for real polynomials,” presented
    at the ISSAC: International Symposium on Symbolic and Algebraic Computation, California,
    USA, 2011, pp. 209–216.'
  ista: 'Kerber M, Sagraloff M. 2011. Root refinement for real polynomials. ISSAC:
    International Symposium on Symbolic and Algebraic Computation, 209–216.'
  mla: Kerber, Michael, and Michael Sagraloff. <i>Root Refinement for Real Polynomials</i>.
    Springer, 2011, pp. 209–16, doi:<a href="https://doi.org/10.1145/1993886.1993920">10.1145/1993886.1993920</a>.
  short: M. Kerber, M. Sagraloff, in:, Springer, 2011, pp. 209–216.
conference:
  end_date: 2011-06-11
  location: California, USA
  name: 'ISSAC: International Symposium on Symbolic and Algebraic Computation'
  start_date: 2011-06-08
date_created: 2018-12-11T12:02:43Z
date_published: 2011-06-08T00:00:00Z
date_updated: 2021-01-12T07:42:42Z
day: '08'
department:
- _id: HeEd
doi: 10.1145/1993886.1993920
external_id:
  arxiv:
  - '1104.1362'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1104.1362
month: '06'
oa: 1
oa_version: Preprint
page: 209 - 216
publication_status: published
publisher: Springer
publist_id: '3304'
quality_controlled: '1'
scopus_import: 1
status: public
title: Root refinement for real polynomials
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2011'
...