Name
Abstract | ||
|---|---|---|
Let $$\\mathrm {R}$$ R be a real closed field and $$\\mathrm{D}\\subset \\mathrm {R}$$ D ¿ R an ordered domain. We present an algorithm that takes as input a polynomial $$Q \\in \\mathrm{D}[X_{1},\\ldots ,X_{k}]$$ Q ¿ D [ X 1 , ¿ , X k ] and computes a description of a roadmap of the set of zeros, $$\\mathrm{Zer}(Q,\\,\\mathrm {R}^{k}),$$ Zer ( Q , R k ) , of Q in $$\\mathrm {R}^{k}.$$ R k . The complexity of the algorithm, measured by the number of arithmetic operations in the ordered domain $$\\mathrm{D},$$ D , is bounded by $$d^{O(k \\sqrt{k})},$$ d O ( k k ) , where $$d = \\deg (Q)\\ge 2.$$ d = deg ( Q ) ¿ 2 . As a consequence, there exist algorithms for computing the number of semialgebraically connected components of a real algebraic set, $$\\mathrm{Zer}(Q,\\,\\mathrm {R}^{k}),$$ Zer ( Q , R k ) , whose complexity is also bounded by $$d^{O(k \\sqrt{k})},$$ d O ( k k ) , where $$d = \\deg (Q)\\ge 2.$$ d = deg ( Q ) ¿ 2 . The best previously known algorithm for constructing a roadmap of a real algebraic subset of $$\\mathrm {R}^{k}$$ R k defined by a polynomial of degree d has complexity $$d^{O(k^{2})}.$$ d O ( k 2 ) . |
Year | DOI | Venue |
|---|---|---|
2012 | https://doi.org/10.1007/s10208-014-9212-1 | Foundations of Computational Mathematics |
Keywords | DocType | Volume |
Roadmaps,Real algebraic variety,Baby step-giant step,Primary 14Q20,Secondary 14P05,68W05 | Journal | 14 |
Issue | ISSN | Citations |
6 | 1615-3375 | 9 |
PageRank | References | Authors |
0.51 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Saugata Basu | 1 | 429 | 64.79 |
| Marie-Françoise Roy | 2 | 411 | 56.93 |
| Mohab Safey El Din | 3 | 450 | 35.64 |
| Éric Schost | 4 | 712 | 58.00 |