##### Files:

[PDF] 262.1kB [gzipped postscript] 330.4kB

##### 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 Feb 06, 2017 11:45:57