Computing the Homology of Semialgebraic Sets. II: General Formulas

Peter Bürgisser, Felipe Cucker, Josué Tonelli-Cueto

Introduction

Semialgebraic sets—geometric shapes defined by polynomial equations and inequalities—are central to fields ranging from robotics to computational geometry. Determining their homology (Betti numbers and torsion coefficients) allows us to understand their fundamental topological features, such as the number of connected components or "holes."

Historically, this task relied on symbolic algorithms like Cylindrical Algebraic Decomposition (CAD). However, CAD suffers from "doubly exponential" complexity ($2^{2^n}$), rendering it impractical for even moderately sized dimensions. This paper presents a transformative numerical algorithm that achieves "weak exponential time" complexity, effectively bypassing this long-standing bottleneck.

The Gabrielov-Vorobjov (GV) Approximation

The core challenge in handling general semialgebraic sets is their potential "messiness"—they can be open, non-compact, or have components that are infinitesimally close. The authors overcome this using the Gabrielov-Vorobjov (GV) construction.

This technique replaces an arbitrary semialgebraic set with a sequence of closed, compact "blocks." These blocks are homotopy equivalent to the original set but are significantly easier to process numerically.

The GV construction replaces complex sets with a sequence of topologically equivalent closed blocks.

Numerical Stability and "Thickening"

Unlike symbolic methods that require exact logic, this algorithm utilizes numerical analysis. It approximates the target set $S(f, \Phi)$ by "thickening" it into a set $\Gamma B$. The degree of thickening is controlled by the system's condition number ($\kappa$), which measures how sensitive the topology is to small perturbations in the polynomial coefficients.

Comparison between the original set $S(f, \Phi)$ and its thickened approximations $\Gamma B$ at different parameter levels.

By sampling a grid of points from these approximations and constructing a Cech complex, the algorithm can compute the exact homology using standard linear algebra. The authors demonstrate that this approach is numerically stable, ensuring that small rounding errors do not compromise the topological results.

Breaking the Complexity Barrier

The most significant result of this work is the reduction in computational complexity. While the algorithm's performance depends on the condition number, the authors prove that "ill-posed" inputs are extremely rare. For almost all inputs, the algorithm runs in single exponential time ($2^{poly(n)}$).

Specifically, the cost is bounded by $size(\Phi)q^{O(n)}(nD\kappa_{aff}(p))^{O(n^2)}$. This shift from doubly to single exponential time represents a massive leap for the practical applicability of topological computations in higher dimensions.

Conclusion and Future Directions

This research provides the first numerical algorithm capable of computing the homology of any semialgebraic set. While the runtime is sensitive to the condition number, the authors suggest a hybrid approach—running this numerical method in parallel with symbolic CAD—to combine the speed of numerical analysis with the worst-case guarantees of symbolic logic. Future work will focus on translating these real-number complexity results into bit complexity for practical computer implementations.

Summary updated

Abstract

We describe and analyze a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of semialgebraic sets given by Boolean formulas. The algorithm 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. This extends the previous work of the authors in arXiv:1807.06435 to arbitrary semialgebraic sets. All previous algorithms proposed for this problem have doubly exponential complexity.
BibTeX
@article{burgisser2021computing,
  author = {Peter Bürgisser and Felipe Cucker and Josué Tonelli-Cueto},
  title = {{Computing the Homology of Semialgebraic Sets. II: General Formulas}},
  journal = {Found. Comput. Math.},
  year = {2021},
  doi = {10.1007/s10208-020-09483-8},
}
Figure