Computing the homology of semialgebraic sets. I: Lax formulas (Q2291730)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computing the homology of semialgebraic sets. I: Lax formulas |
scientific article |
Statements
Computing the homology of semialgebraic sets. I: Lax formulas (English)
0 references
31 January 2020
0 references
In the article, the authors present an algorithm for computing the Betti numbers and torsion coefficients of closed semialgebraic sets. Semialgebraic sets are subsets of \(\mathbb{R}^n\) defined by Boolean combinations (i.e., a sequence of unions, intersections, and complements) of polynomial equalities and inequalities. The class of these sets is closed under unions, intersections, complements, and projections as well as under taking images and preimages of polynomial maps. Semialgebraic sets play a distinguished role in several branches of mathematics including real algebraic geometry, complexity theory, mathematical programming, robotics, etc. In this article, the authors focus on semialgebraic sets given by Boolean formulas without negations over lax polynomial inequalities i.e., they are defined by only unions and intersections of the atomic sets. In contrast to the doubly exponential complexity of previous algorithms for computing the sequence of homology groups of semialgebraic sets, the algorithm proposed in this article works in weak exponential time. This means that outside a subset of data having exponentially small measure, the cost of the algorithm is single exponential in the size of the data.
0 references
homology groups
0 references
weak complexity
0 references
numerical algorithms
0 references
lax Boolean combinations
0 references
0 references
0 references
0 references
0 references