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
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references