Improved complexity bounds for real root isolation using Continued Fractions

Details Improved complexity bounds for real root isolation using Continued Fractions Improved complexity bounds for real root isolation using Continued Fractions

2010-10-11

arxiv.org/abs/1010.2006v2

Computer Science

Symbolic Computation

The improved bound bound that was claimed in an earlier version is removed, since there was an error in the proof

Scientific paper

We consider the problem of isolating the real roots of a square-free polynomial with integer coefficients using (variants of) the continued fraction algorithm (CF). We introduce a novel way to compute a lower bound on the positive real roots of univariate polynomials. This allows us to derive a worst case bound of $\sOB(d^6 + d^4\tau^2 + d^3\tau^2)$ for isolating the real roots of a polynomial with integer coefficients using the classic variant \cite{Akritas:implementation} of CF, where $d$ is the degree of the polynomial and $\tau$ the maximum bitsize of its coefficients. This improves the previous bound of Sharma \cite{sharma-tcs-2008} by a factor of $d^3$ and matches the bound derived by Mehlhorn and Ray \cite{mr-jsc-2009} for another variant of CF; it also matches the worst case bound of the subdivision-based solvers.

Affiliated with

Also associated with

No associations

Rating

Improved complexity bounds for real root isolation using Continued Fractions 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 Improved complexity bounds for real root isolation using Continued Fractions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved complexity bounds for real root isolation using Continued Fractions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-658192