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.
Type de document :
Rapport
[Research Report] RR2010, Aarhus Universitet. 2010
Liste complète des métadonnées

https://hal.inria.fr/inria-00524834
Contributeur : Elias Tsigaridas <>
Soumis le : mercredi 1 juin 2011 - 18:48:41
Dernière modification le : samedi 17 septembre 2016 - 01:20:17
Document(s) archivé(s) le : dimanche 4 décembre 2016 - 02:33:58

Fichiers

CF.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

135

Téléchargements de fichiers

85