HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

On the complexity of real root isolation using Continued Fractions

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 improve the previously known bound by a factor of $d \tau$, where $d$ is the polynomial degree and $\tau$ bounds the coefficient bit size, thus matching the current record complexity for real root isolation by exact methods (Sturm, Descartes and Bernstein subdivision). Namely our complexity bound is $\sOB(d^4 \tau^2)$ using a standard bound on the expected bit size of the integers in the continued fraction expansion. Moreover, using a homothetic transformation we improve the expected complexity bound to $\sOB( d^3 \tau)$ under the assumption that $d = \OO( \tau)$. We compute the multiplicities within the same complexity and extend the algorithm to non square-free polynomials. Finally, we present an efficient open-source \texttt{C++} implementation and illustrate its completeness and efficiency as compared to other available software. For this we use polynomials with coefficient bit size up to 8000 bits and degree up to 1000.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00116990
Contributor : Elias Tsigaridas Connect in order to contact the contributor
Submitted on : Monday, December 11, 2006 - 12:11:18 PM
Last modification on : Friday, February 4, 2022 - 3:18:37 AM
Long-term archiving on: : Friday, September 24, 2010 - 1:56:19 PM

File

RR-6059.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00116990, version 6

Collections

Citation

Elias P. Tsigaridas, Ioannis Emiris. On the complexity of real root isolation using Continued Fractions. [Research Report] RR-6059, INRIA. 2006, pp.22. ⟨inria-00116990v6⟩

Share

Metrics

Record views

137

Files downloads

208