Nearly Optimal Refinement of Real Roots of a Univariate Polynomial

Abstract : We assume that a real square-free polynomial $A$ has a degree $d$, a maximum coefficient bitsize $\tau$ and a real root lying in an isolating interval and having no nonreal roots nearby (we quantify this assumption). Then we combine the {\em Double Exponential Sieve} algorithm (also called the {\em Bisection of the Exponents}), the bisection, and Newton iteration to decrease the width of this inclusion interval by a factor of $t=2^{-L}$. The algorithm has Boolean complexity $O_B~(d^2 \tau + d L )$. This substantially decreases the known bound $O_B~(d^3 +d^2L)$ and is optimal up to a polylogarithmic factor. Furthermore we readily extend our algorithm to support the same upper bound on the complexity of the refinement of $r$ real roots, for any $r\le d$, by incorporating the known efficient algorithms for multipoint polynomial evaluation. The main ingredient for the latter is an efficient algorithm for (approximate) polynomial division; we present a variation based on structured matrix computation with quasi-optimal Boolean complexity.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2015, 74, pp.181-204. 〈10.1016/j.jsc.2015.06.009〉
Liste complète des métadonnées

Littérature citée [55 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00960896
Contributeur : Elias Tsigaridas <>
Soumis le : lundi 28 décembre 2015 - 23:04:21
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : samedi 29 avril 2017 - 11:55:24

Fichier

pt-refine-jsc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Victor Y. Pan, Elias Tsigaridas. Nearly Optimal Refinement of Real Roots of a Univariate Polynomial. Journal of Symbolic Computation, Elsevier, 2015, 74, pp.181-204. 〈10.1016/j.jsc.2015.06.009〉. 〈hal-00960896v2〉

Partager

Métriques

Consultations de la notice

431

Téléchargements de fichiers

149