Computing the Homology of Semialgebraic Sets. I: Lax Formulas
Computing the Homology of Semialgebraic Sets. I: Lax Formulas
复制标题
计算半代数集的同调。
DOI：
10.1007/s10208-019-09418-y
复制
发表时间：
2018
影响因子：
3
通讯作者：
Josué Tonelli
中科院分区：
文献类型：
--
作者：
Peter Bürgisser;F. Cucker;Josué Tonelli
我们描述和分析的算法计算的同源性（贝蒂数和扭系数）的封闭半代数集的布尔公式没有否定宽松的多项式不等式。该算法工作在弱指数时间。这意味着在具有指数小度量的数据子集之外，算法的成本在数据大小上是单指数的。以往解决该问题的算法都具有双指数复杂度。因此，我们的算法代表了一个指数加速超过国家的最先进的算法的所有输入数据以外的一组，指数快速消失。
We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of closed semialgebraic sets given by Boolean formulas without negations over lax polynomial inequalities. 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. All previous algorithms solving this problem have doubly exponential complexity. Our algorithm thus represents an exponential acceleration over state-of-the-art algorithms for all input data outside a set that vanishes exponentially fast.