Elias' Article

On the complexity of real root isolation using Continued Fractions.
Elias P. Tsigaridas and Ioannis Z. Emiris.
Theor. Comput. Sci., 392:158–173, 2008.

• Home
• Research
• Teaching
• Contact

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.

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