Root refinement for real polynomials
Kerber, Michael
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
text
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