Computing the Homology of Semialgebraic Sets. II: General Formulas
Computing the Homology of Semialgebraic Sets. II: General Formulas
复制标题
计算半代数集的同调。
DOI：
10.1007/s10208-020-09483-8
复制
发表时间：
2019
影响因子：
3
通讯作者：
Josué Tonelli
中科院分区：
文献类型：
--
作者：
Peter Bürgisser;F. Cucker;Josué Tonelli
我们描述和分析了一个数值算法计算的同调（贝蒂数和扭系数）的半代数集的布尔公式。该算法工作在弱指数时间。这意味着在具有指数小度量的数据子集之外，算法的成本在数据大小上是单指数的。这将第一部分的工作扩展到任意半代数集。所有以前的算法提出了这个问题有双指数复杂度。
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 work in Part I to arbitrary semialgebraic sets. All previous algorithms proposed for this problem have doubly exponential complexity.
DOI：
10.1145/3275242
发表时间：
2018
期刊：
Journal of the ACM (JACM)
影响因子：
--
作者：
P. Bürgisser;F. Cucker;P. Lairez
通讯作者：
P. Lairez
实多项式系统的概率条件数估计 I：更广泛的分布族
影响因子：
3
作者：
Ergür, Alperen A.;Paouris, Grigoris;Rojas, J. Maurice
通讯作者：
Rojas, J. Maurice