Computing the Top Betti Numbers of Semialgebraic Sets Defined by Quadratic Inequalities in Polynomial Time |
| |
Authors: | Saugata Basu |
| |
Institution: | (1) School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA |
| |
Abstract: | For any ℓ>0, we present an algorithm which takes as input a semi-algebraic set, S, defined by P
1≤0,…,P
s
≤0, where each P
i
∈RX
1,…,X
k
] has degree≤2, and computes the top ℓ Betti numbers of S, b
k−1(S),…,b
k−ℓ
(S), in polynomial time. The complexity of the algorithm, stated more precisely, is
. For fixed ℓ, the complexity of the algorithm can be expressed as
, which is polynomial in the input parameters s and k. To our knowledge this is the first polynomial time algorithm for computing nontrivial topological invariants of semialgebraic
sets in R
k
defined by polynomial inequalities, where the number of inequalities is not fixed and the polynomials are allowed to have
degree greater than one. For fixed s, we obtain, by letting ℓ=k, an algorithm for computing all the Betti numbers of S whose complexity is
.
An erratum to this article can be found at |
| |
Keywords: | Betti numbers Quadratic inequalities Semialgebraic sets |
本文献已被 SpringerLink 等数据库收录! |
|