##### Abstract:

We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued fraction expansion of real algebraic numbers. One motivation is to explain the method's good performance in practice. %% We derive an expected complexity bound of $\sOB(d^6 + d^4 \tau^2)$, where $d$ is the polynomial degree and $\tau$ bounds the coefficient bit size, using a standard bound on the expected bit size of the integers in the continued fraction expansion, thus matching the current worst-case complexity bound for real root isolation by exact methods (Sturm, Descartes and Bernstein subdivision). %% Moreover, using a homothetic transformation we improve the expected complexity bound to $\sOB( d^3 \tau)$. We compute the multiplicities within the same complexity and extend the algorithm to non square-free polynomials. %% Finally, we present an open-source \textttC++ implementation in the algebraic library \synaps, and illustrate its completeness and efficiency as compared to some other available software. For this we use polynomials with coefficient bit size up to 25000 bits and degree up to 2000.

##### BibTeX:
@Article{te-tcs-2008,
author =       {Elias~P. Tsigaridas and Ioannis~Z. Emiris},
title =        {{On the complexity of real root isolation using
Continued Fractions}},
journal =      TCS,
volume =       392,
pages =        {158--173},
year =         2008,
editor =       {L. Bus{\'e} and M. Elkadi and B. Mourrain},
abstract =     " We present algorithmic, complexity and
implementation results concerning real root
isolation of integer univariate polynomials using
the continued fraction expansion of real algebraic
numbers.  One motivation is to explain the method's
good performance in practice.  %% We derive an
expected complexity bound of $\sOB(d^6 + d^4 \tau^2)$, where $d$ is the polynomial degree and
$\tau$ bounds the coefficient bit size, using a
standard bound on the expected bit size of the
integers in the continued fraction expansion, thus
matching the current worst-case complexity bound for
real root isolation by exact methods (Sturm,
Descartes and Bernstein subdivision).  %% Moreover,
using a homothetic transformation we improve the
expected complexity bound to $\sOB( d^3 \tau)$.  We
compute the multiplicities within the same
complexity and extend the algorithm to non
square-free polynomials.  %% Finally, we present an
open-source \texttt{C++} implementation in the
algebraic library \synaps, and illustrate its
completeness and efficiency as compared to some
other available software.  For this we use
polynomials with coefficient bit size up to 25\,000
bits and degree up to 2\,000.",
}


Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Mon Mar 12, 2018 14:23:33