##### Files:

(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 Mon Mar 12, 2018 14:23:33