A baby step-giant step roadmap algorithm for general algebraic sets

2012/01/31 by Saugata Basu, Marie-Françoise Roy, Basu, Saugata +5 · 2 citations
Computer Science · Mathematics · #68W05 #Algebraic Geometry (math.AG) #Coding theory and cryptography #Commutative Algebra and Its Applications #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation #Primary 14Q20 #Secondary 14P05 #Symbolic Computation (cs.SC)

paper · pdf · doi:10.48550/arxiv.1201.6439

openalex publication_date 2012/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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₁,…,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 operations 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 previously 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(k2).

Cited by

• ENSI: Efficient Non-Interactive Secure Inference for Large Language Models
• On the convergence of critical points on real algebraic sets and applications to optimization

Related

• Computing roadmaps in unbounded smooth real algebraic sets II: algorithm and complexity
• A nearly optimal algorithm for deciding connectivity queries in smooth\n and bounded real algebraic sets
• A baby steps/giant steps Monte Carlo algorithm for computing roadmaps in smooth compact real hypersurfaces
• Polynomial-time computing over quadratic maps I: sampling in real algebraic sets
• A probabilistic algorithm to compute the real dimension of a semi-algebraic set