A Baby Step–Giant Step Roadmap Algorithm for General Algebraic Sets

Abstract : Let R be a real closed field and D ⊂ R an ordered domain. We give an algorithm that takes as input a polynomial Q ∈ D[X 1 , . . . , X k ], and computes a description of a roadmap of the set of zeros, Zer(Q, R k), of Q in R k . The complexity of the algorithm, measured by the number of arithmetic opera-tions in the ordered domain D, is bounded by d O(k √ k) , where d = deg(Q) ≥ 2. As a consequence, there exist algorithms for computing the number of semi-algebraically connected components of a real algebraic set, Zer(Q, R k), whose complexity is also bounded by d O(k √ k) , where d = deg(Q) ≥ 2. The best pre-viously known algorithm for constructing a roadmap of a real algebraic subset of R k defined by a polynomial of degree d has complexity d O(k 2) .
Type de document :
Article dans une revue
Foundations of Computational Mathematics, Springer Verlag, 2014, 14 (6), pp.1117 - 1172. <10.1007/s10208-014-9212-1>
Liste complète des métadonnées


https://hal.inria.fr/hal-01096209
Contributeur : Mohab Safey El Din <>
Soumis le : mercredi 17 décembre 2014 - 07:45:23
Dernière modification le : mercredi 2 août 2017 - 10:10:55
Document(s) archivé(s) le : lundi 23 mars 2015 - 14:38:44

Fichier

brss_revised-may-15-2014.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Saugata Basu, Marie-Françoise Roy, Mohab Safey El Din, Eric Schost. A Baby Step–Giant Step Roadmap Algorithm for General Algebraic Sets. Foundations of Computational Mathematics, Springer Verlag, 2014, 14 (6), pp.1117 - 1172. <10.1007/s10208-014-9212-1>. <hal-01096209>

Partager

Métriques

Consultations de
la notice

276

Téléchargements du document

96