Root refinement for real polynomials

Kerber M, Sagraloff M. 2011. Root refinement for real polynomials. ISSAC: International Symposium on Symbolic and Algebraic Computation, 209–216.

Download (ext.)

Conference Paper | Published | English

Scopus indexed
Author
Kerber, MichaelISTA ; Sagraloff, Michael
Department
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.
Publishing Year
Date Published
2011-06-08
Page
209 - 216
Conference
ISSAC: International Symposium on Symbolic and Algebraic Computation
Conference Location
California, USA
Conference Date
2011-06-08 – 2011-06-11
IST-REx-ID

Cite this

Kerber M, Sagraloff M. Root refinement for real polynomials. In: Springer; 2011:209-216. doi:10.1145/1993886.1993920
Kerber, M., & 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. https://doi.org/10.1145/1993886.1993920
Kerber, Michael, and Michael Sagraloff. “Root Refinement for Real Polynomials,” 209–16. Springer, 2011. https://doi.org/10.1145/1993886.1993920.
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.
Kerber M, Sagraloff M. 2011. Root refinement for real polynomials. ISSAC: International Symposium on Symbolic and Algebraic Computation, 209–216.
Kerber, Michael, and Michael Sagraloff. Root Refinement for Real Polynomials. Springer, 2011, pp. 209–16, doi:10.1145/1993886.1993920.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 1104.1362

Search this title in

Google Scholar