On the Boolean complexity of real root refinement

Victor Pan 1 Elias Tsigaridas 2
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
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 ${\widetilde{\mathcal{O}}_B}(d^2 \tau + d L )$. Our algorithms support the same complexity bound for the refinement of $r$ roots, for any $r\le d$.
Type de document :
Communication dans un congrès
ISSAC 2013 - International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, United States. ACM, 2013, <10.1145/2465506.2465938>
Liste complète des métadonnées


https://hal.inria.fr/hal-00816214
Contributeur : Elias Tsigaridas <>
Soumis le : jeudi 25 avril 2013 - 14:10:08
Dernière modification le : samedi 7 novembre 2015 - 01:06:06
Document(s) archivé(s) le : lundi 3 avril 2017 - 23:38:14

Fichier

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

Identifiants

Collections

Citation

Victor Pan, Elias Tsigaridas. On the Boolean complexity of real root refinement. ISSAC 2013 - International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, United States. ACM, 2013, <10.1145/2465506.2465938>. <hal-00816214v3>

Partager

Métriques

Consultations de
la notice

342

Téléchargements du document

217