Mathematics – Algebraic Geometry
Scientific paper
2012-01-31
Mathematics
Algebraic Geometry
50 pages
Scientific paper
Let $\R$ be a real closed field and $\D \subset \R$ an ordered domain. We give an algorithm that takes as input a polynomial $Q \subset \D[X_1,...,X_k]$, and computes a description of a roadmap of the set of zeros, $\ZZ(Q,\R^k)$, of $Q$ in $\R^k$. The complexity of the algorithm, measured by the number of arithmetic operations in the domain $\D$, is bounded by $d^{O(k \sqrt{k})}$, where $d = deg(Q)\ge 2$. As a consequence, there exist algorithms for computing the number of semi-algebraically connected components of a real algebraic set, $\ZZ(Q,\R^k)$, whose complexity is also bounded by $d^{O(k \sqrt{k})}$, where $d = deg(Q)\ge 2$. The best previously known algorithm for constructing a roadmap of a real algebraic subset of $\R^k$ defined by a polynomial of degree $d$ had complexity $d^{O(k^2)}$.
Basu Saugata
El Din Mohab Safey
Roy Marie-Françoise
Schost Éric
No associations
LandOfFree
A baby step-giant step roadmap algorithm for general algebraic sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A baby step-giant step roadmap algorithm for general algebraic sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A baby step-giant step roadmap algorithm for general algebraic sets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-56497