Root Refinement for Real Polynomials

Details Root Refinement for Real Polynomials Root Refinement for Real Polynomials

2011-04-07

arxiv.org/abs/1104.1362v1

Computer Science

Symbolic Computation

Scientific paper

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 of $2^{-L}$ or less, 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 considering finite approximations of the polynomial coefficients 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, size and separation of the roots, that is, parameters exclusively related to the geometric location of the roots. 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.

Affiliated with

Also associated with

No associations

Rating

Root Refinement for Real Polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Root Refinement for Real Polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Root Refinement for Real Polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-718063