Computer Science – Symbolic Computation
Scientific paper
2010-10-08
Computer Science
Symbolic Computation
This paper has been withdrawn by the author due to a new version available at arXiv:1010.2006
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 of CF, where $d$ is the degree of the polynomial and $\tau$ the maximum bitsize of its coefficients. This improves the previous bound by 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. We present a new variant of CF, we call it iCF, that isolates the real roots of a polynomial with integer coefficients in $\sOB(d^5+d^4\tau)$, thus improving the current known bound for the problem by a factor of $d$. If the polynomial has only real roots, then our bound becomes $\sOB(d^4+d^3\tau+ d^2\tau^2)$, thus matching the bound of the numerical algorithms by Reif \cite{r-focs-1993} and by Ben-Or and Tiwari \cite{bt-joc-1990}. Actually the latter bound holds in a more general setting, that is under the rather mild assumption that $\Omega(d/\lg^c{d})$, where $c\geq 0$ is a constant, roots contribute to the sign variations of the coefficient list of the polynomial. This is the only bound on exact algorithms that matches the one of the numerical algorithms by Pan \cite{Pan02jsc} and Sch\"onhage \cite{Sch82}. To our knowledge the presented bounds are the best known for the problem of real root isolation for algorithms based on exact computations.
No associations
LandOfFree
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.
Profile ID: LFWR-SCP-O-487039