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

DOI10.1016/J.JALGEBRA.2008.09.043zbMATH Open1171.14040arXiv0806.3911OpenAlexW2001918102WikidataQ56859918 ScholiaQ56859918MaRDI QIDQ1024388FDOQ1024388

Dmitrii V. Pasechnik, Marie-Françoise Roy, Saugata Basu

Publication date: 17 June 2009

Published in: Journal of Algebra (Search for Journal in Brave)

Abstract: Let $R$ be a real closed field, $mathcalQsubsetR[Y_1,\mathrm{...},Y_{e}ll,X_1,\mathrm{...},X_k],$ with $$, and $mathcalPsubsetR[X_1,\mathrm{...},X_k]$ with $$. Let $Ssubset{R}^{ell+k}$ be a semi-algebraic set defined by a Boolean formula without negations, with atoms $P=0,Pgeq0,Pleq0,PinmathcalPcupmathcalQ$. We describe an algorithm for computing the the Betti numbers of $S$. The complexity of the algorithm is bounded by $(ellsmd{)}^{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.

Full work available at URL: https://arxiv.org/abs/0806.3911

Recommendations

• Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials
• Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time
• Betti number bounds, applications and algorithms
• Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities
• On the Betti numbers of semialgebraic sets defined by few quadratic inequalities
• scientific article; zbMATH DE number 2209741
• Algorithmic Semi-algebraic Geometry and Topology -- Recent Progress and Open Problems
• Computing the Euler-Poincaré characteristics of sign conditions
• Complexity of deciding connectivity in real algebraic sets
• Description of the connected components of a semialgebraic set in single exponential time

zbMATH Keywords

triangulationBetti numbersreal closed fieldsemi-algebraic setscell complexquadratic inequalitiesinfinitesimal elements

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Topology of real algebraic varieties (14P25) Semialgebraic sets and related spaces (14P10)

Cites Work

• Title not available (Why is that?)
• On the Betti numbers of semialgebraic sets defined by few quadratic inequalities
• Title not available (Why is that?)
• On the Betti Numbers of Real Varieties
• Algorithms in real algebraic geometry
• Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials
• A Vietoris Mapping Theorem for Homotopy
• Topology of quadratic maps and Hessians of smooth maps
• Polynomial-time computing over quadratic maps i: sampling in real algebraic sets
• Feasibility testing for systems of real quadratic equations
• Title not available (Why is that?)
• A sharper estimate on the Betti numbers of sets defined by quadratic inequalities
• Computing Roadmaps of General Semi-Algebraic Sets
• Computing roadmaps of semi-algebraic sets on a variety
• Construction of roadmaps in semi-algebraic sets
• Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time
• Counting connected components of a semialgebraic set in subexponential time
• Betti numbers of semialgebraic sets defined by quantifier-free formulae
• On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets
• Algorithmic Semi-algebraic Geometry and Topology -- Recent Progress and Open Problems
• Computing the first Betti number of a semi-algebraic set
• Description of the connected components of a semialgebraic set in single exponential time
• Computing the first few Betti numbers of semi-algebraic sets in single exponential time

Cited In (7)

• A complexity theory of constructible functions and sheaves
• Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets
• Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials
• Geodesic diameter of sets defined by few quadratic equations and inequalities
• Computing the Betti numbers of arrangements via spectral sequences
• Bounding the equivariant Betti numbers of symmetric semi-algebraic sets
• Computing the first Betti number of a semi-algebraic set

This page was built for publication: Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024388)