论文标题
在半代数图和图表上计算同源性函数
Computing the homology functor on semi-algebraic maps and diagrams
论文作者
论文摘要
开发一种用于计算具有单一指数复杂性的半代数集的算法数量，它是算法半几何学的圣杯，只有部分结果是已知的。在本文中，我们考虑了在封闭式和有限的半代数集之间的半代数映射$ f：x \ rightarrow y $下计算图像的更普遍的问题。 For every fixed $\ell \geq 0$ we give an algorithm with singly exponential complexity that computes bases of the homology groups $\mathrm{H}_i(X), \mathrm{H}_i(Y)$ (with rational coefficients) and a matrix with respect to these bases of the induced linear maps $ \ mathrm {h} _i（f）：\ mathrm {h} _i（x）\ rightarrow \ rightarrow \ mathrm {h} _i（y），0 \ leq i \ leq i \ leq \ ell $。我们将此算法推广到封闭和有界半代数集之间的地图的更通用（Zigzag）图，并给出了一个单独的指数算法，用于在此图上计算同源性函数。这使我们能够给出具有单一指数复杂性的算法，以计算小小的较小维度的半代数锯齿形持续同源性的条形码。
Developing an algorithm for computing the Betti numbers of semi-algebraic sets with singly exponential complexity has been a holy grail in algorithmic semi-algebraic geometry and only partial results are known. In this paper we consider the more general problem of computing the image under the homology functor of a semi-algebraic map $f:X \rightarrow Y$ between closed and bounded semi-algebraic sets. For every fixed $\ell \geq 0$ we give an algorithm with singly exponential complexity that computes bases of the homology groups $\mathrm{H}_i(X), \mathrm{H}_i(Y)$ (with rational coefficients) and a matrix with respect to these bases of the induced linear maps $\mathrm{H}_i(f):\mathrm{H}_i(X) \rightarrow \mathrm{H}_i(Y), 0 \leq i \leq \ell$. We generalize this algorithm to more general (zigzag) diagrams of maps between closed and bounded semi-algebraic sets and give a singly exponential algorithm for computing the homology functors on such diagrams. This allows us to give an algorithm with singly exponential complexity for computing barcodes of semi-algebraic zigzag persistent homology in small dimensions.
