Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Reports

Improved complexity bounds for real root isolation using Continued Fractions

Abstract : We consider the problem of isolating the real roots of a square-free polynomial with integer coefficients using (variants of) the continued fraction algorithm (CF). We introduce a novel way to compute a lower bound on the positive real roots of univariate polynomials. This allows us to derive a worst case bound of $\sOB( d^6 + d^4\tau^2 + d^3\tau^2)$ for isolating the real roots of a polynomial with integer coefficients using the classic variant \cite{Akritas:implementation} 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 \cite{sharma-tcs-2008} by a factor of $d^3$ and matches the bound derived by Mehlhorn and Ray \cite{mr-jsc-2009} for another variant of CF; it also matches the worst case bound of the subdivision-based solvers.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00524834
Contributor : Elias Tsigaridas Connect in order to contact the contributor
Submitted on : Wednesday, June 1, 2011 - 6:48:41 PM
Last modification on : Saturday, September 17, 2016 - 1:20:17 AM
Long-term archiving on: : Sunday, December 4, 2016 - 2:33:58 AM

Files

CF.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00524834, version 4
  • ARXIV : 1010.2006

Collections

Citation

Elias Tsigaridas. Improved complexity bounds for real root isolation using Continued Fractions. [Research Report] RR2010, Aarhus Universitet. 2010. ⟨inria-00524834v4⟩

Share

Metrics

Record views

100

Files downloads

97