(unavailable)

Abstract:

We consider the problem of isolating the real roots of a square-free polynomial with integer coefficients using the classic variant of the continued fraction algorithm (CF), introduced by Akritas. We compute a lower bound on the positive real roots of univariate polynomials using exponential search. This allows us to derive a worst case bound of $\sOB( d^4\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 of Sharma by a factor of $d^3$ and matches the bound derived by Mehlhorn and Ray for another variant of CF which is combined with subdivision; it also matches the worst case bound of the classical subdivision-based solvers \funcsturm, \funcdescartes, and \funcbernstein.

BibTeX:
@Article{t-tcs-12,
title =        {{ Improved bounds for the CF algorithm}},
author =       {Elias~P. Tsigaridas},
journal =      TCS,
volume =       479,
number =       0,
year =         2013,
pages =        {120--126},
abstract =     "We consider the problem of isolating the real roots
of a square-free polynomial with integer
coefficients using the classic variant of the
continued fraction algorithm (CF), introduced by
Akritas.  We compute a lower bound on the positive
real roots of univariate polynomials using
exponential search. This allows us to derive a worst
case bound of $\sOB( d^4\tau^2)$ for isolating the
real roots of a polynomial with integer coefficients
using the {\em 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 of Sharma by a factor of $d^3$ and
matches the bound derived by Mehlhorn and Ray for
another variant of CF which is combined with
subdivision; it also matches the worst case bound of
the classical subdivision-based solvers
\func{sturm}, \func{descartes}, and
\func{bernstein}.",
}


Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 25, 2017 11:23:11