Files:
Abstract:
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 \citesharma-tcs-2008 by a factor of $d^3$ and matches the bound derived by Mehlhorn and Ray \citemr-jsc-2009 for another variant of CF; it also matches the worst case bound of the subdivision-based solvers.
BibTeX:
@InProceedings{t-macis-icf-11,
title = {{Improved complexity bounds for real root isolation
using Continued Fractions}},
author = {Elias~P. Tsigaridas},
booktitle = "Proc. 4th Int'l Conf. on Mathematical Aspects of
Computer Information Sciences (MACIS)",
year = 2011,
address = {Beijing, China},
month = {Oct},
editor = " S. Ratschan",
pages = "226--237",
url = {http://arxiv.org/abs/1010.2006},
abstract = "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.",
}
Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02