Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials

Abstract

Let $\mathbb{R}$ be a real closed field, $\mathcal{Q}\subset \mathbb{R}[Y_1,...,Y_{\ell },X_1,...,X_k],$ with $ °_{Y}(Q) \leq 2, °_{X}(Q) \leq d, Q \in {\mathcal Q}, #({\mathcal Q})=m$, and $\mathcal{P}\subset \mathbb{R}[X_1,...,X_k]$ with $°_{X}(P) \leq d, P \in {\mathcal P}, #({\mathcal P})=s$. Let $S\subset {\mathbb{R}}^{\ell +k}$ be a semi-algebraic set defined by a Boolean formula without negations, with atoms $P=0,P\ge 0,P\le 0,P\in \mathcal{P}\cup \mathcal{Q}$. We describe an algorithm for computing the the Betti numbers of $S$. The complexity of the algorithm is bounded by $(\ell smd{)}^{2^{O(m+k)}}$. The complexity of the algorithm interpolates between the doubly exponential time bounds for the known algorithms in the general case, and the polynomial complexity in case of semi-algebraic sets defined by few quadratic inequalities known previously. Moreover, for fixed $m$ and $k$ this algorithm has polynomial time complexity in the remaining parameters.

24 pages, 3 figures

References in corpus (2)

• Polynomial-time computing over quadratic maps I: sampling in real algebraic sets
• Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time

Cited by in corpus (7)

• Algorithms in Real Algebraic Geometry: A Survey
• A complexity theory of constructible functions and sheaves
• Complexity of intersections of real quadrics and topology of symmetric determinantal varieties
• Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets
• Convex pencils of real quadratic forms
• Bounds on the individual Betti numbers of complex varieties, stability and algorithms
• Geodesic diameter of sets defined by few quadratic equations and inequalities