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) .
Document type :
Journal articles
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01096209
Contributor : Mohab Safey El Din <>
Submitted on : Wednesday, December 17, 2014 - 7:45:23 AM
Last modification on : Friday, May 24, 2019 - 5:30:44 PM
Long-term archiving on : Monday, March 23, 2015 - 2:38:44 PM

File

brss_revised-may-15-2014.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

523

Files downloads

219