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

DOI10.1016/J.JALGEBRA.2008.09.043MaRDI QIDQ1024388zbMATH OpenOpenAlexWikidataFDO

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

Publication date 17 June 2009

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

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

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)

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.

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

Cites work

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

Cited in

(10)

• 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 top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time
• Computing the Betti numbers of arrangements via spectral sequences
• Bounding the equivariant Betti numbers of symmetric semi-algebraic sets
• Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities
• Systems of quadratic inequalities
• 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)