When Newton meets Descartes: A Simple and Fast Algorithm to Isolate the Real Roots of a Polynomial

Details When Newton meets Descartes: A Simple and Fast Algorithm to Isolate the Real Roots of a Polynomial When Newton meets Descartes: A Simple and Fast Algorithm to Isolate the Real Roots of a Polynomial

2011-09-28

arxiv.org/abs/1109.6279v1

Computer Science

Symbolic Computation

Scientific paper

We introduce a new algorithm denoted DSC2 to isolate the real roots of a univariate square-free polynomial f with integer coefficients. The algorithm iteratively subdivides an initial interval which is known to contain all real roots of f. The main novelty of our approach is that we combine Descartes' Rule of Signs and Newton iteration. More precisely, instead of using a fixed subdivision strategy such as bisection in each iteration, a Newton step based on the number of sign variations for an actual interval is considered, and, only if the Newton step fails, we fall back to bisection. Following this approach, our analysis shows that, for most iterations, we can achieve quadratic convergence towards the real roots. In terms of complexity, our method induces a recursion tree of almost optimal size O(nlog(n tau)), where n denotes the degree of the polynomial and tau the bitsize of its coefficients. The latter bound constitutes an improvement by a factor of tau upon all existing subdivision methods for the task of isolating the real roots. In addition, we provide a bit complexity analysis showing that DSC2 needs only \tilde{O}(n^3tau) bit operations to isolate all real roots of f. This matches the best bound known for this fundamental problem. However, in comparison to the much more involved algorithms by Pan and Sch\"onhage (for the task of isolating all complex roots) which achieve the same bit complexity, DSC2 focuses on real root isolation, is very easy to access and easy to implement.

Affiliated with

Also associated with

No associations

Rating

When Newton meets Descartes: A Simple and Fast Algorithm to Isolate the Real Roots of a Polynomial 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 When Newton meets Descartes: A Simple and Fast Algorithm to Isolate the Real Roots of a Polynomial, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and When Newton meets Descartes: A Simple and Fast Algorithm to Isolate the Real Roots of a Polynomial will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-44319