Elias' Article

Improved bounds for the CF algorithm.
Elias P. Tsigaridas.
Theor. Comput. Sci., 479(0):120–126, 2013.

• Home
• Research
• Teaching
• Contact

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.

@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 23, 2019 21:41:02