Computational Topology in a Collapsing Universe: Laplacians, Homology, Cohomology
Computational Topology in a Collapsing Universe: Laplacians, Homology, Cohomology
复制标题
坍缩宇宙中的计算拓扑：拉普拉斯算子、同调、上同调
DOI：
10.1137/1.9781611977073.12
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Mitchell Black, William Maxwell
中科院分区：
文献类型：
--
作者：
Mitchell Black, William Maxwell
我们考虑ad维单纯复形K上的各种拓扑问题，假设K ∪ X for XA可折叠单纯复形嵌入在d+1中，具有已知的折叠序列。我们的第一个结果是线性系统L1 x = B的求解器，其中L1是单纯复形K的1-拉普拉斯算子，其中dimH 1（K）= 0，并且K ∪ X for XA可折叠单纯复形嵌入在d +1中，具有已知的折叠序列。我们的算法运行时间为O（nlog 2（nκ/n）），其中n是X中顶点、边和三角形的总数，κ是Laplacian两部分的最大条件数，n κ量化了逼近质量。该结果是Cohen等人[SODA 2014]的推广。我们的拉普拉斯解算器的新技术部分，除了科恩等人描述的机器之外，是一个计算1-圈的有界链的算法，此外，我们还给出了检验（d-1）-圈的零同调和d-上圈的零上同调的快速算法.我们的算法在O（nd）时间内运行，其中是X中d-单形的个数.最后，我们描述了一个算法，从给定的（d-1）-同调基计算一个（d-1）-上同调基KinO（βd-1 nd）时间;βd-1是k的第（d-1）同调群的秩.特别地，我们可以得到嵌入在λ 3 inO中的可折叠复形X的子复形的上同调基（ndlognd+βd-1 n）时间，使用Dey算法计算的同调基[SODA 2019]。对于上述所有问题，如果K ≠ 3且不提供可塌缩超复形X，则我们可以将K展开为可能具有二次复杂度的凸球，已知其是可塌缩的，从而导致接近二次时间算法。
We consider a variety of topology problems on ad-dimensional simplicial complexKgiven thatK∪XforXa collapsible simplicial complex embedded in ℝd+1with known collapsing sequence.Our first result is a solver for the linear systemL1x = b, whereL1is the 1-Laplacian of a simplicial complexKwith dimH1(K) = 0 andK∪XforXa collapsible simplicial complex embedded in ℝ3with a known collapsing sequence. Our algorithm runs inO(nlog2(nκ/∊)) time, wherenis the total number of vertices, edges, and triangles inX, κis the largest condition number of the two parts of the Laplacian, and∊quantifies the approximation quality. This result is a generalization of Cohen et al. [SODA 2014]. The new technical piece of our Laplacian solver, in addition to the machinery described by Cohen et al., is an algorithm to compute a bounding chain of a 1-cycle withink.In addition, we describe faster algorithms for testing null-homology of (d–1)-cycles and null-cohomology ofd-cocycles. Our algorithm runs inO(nd) time, wherendis the number ofd-simplices inX.Finally, we describe an algorithm to compute a (d–1)-cohomology basis from a given (d–1)-homology basis for ad-simplicial complexKinO(βd–1nd) time;βd–1is the rank of the (d–1)st homology group ofk. In particular, we can obtain a cohomology basis for subcomplexes of a collapsible complexXembedded in ℝ3inO(ndlognd+βd–1n) time using a homology basis computed by the algorithm of Dey [SODA 2019].For all of the problems above, ifK∪ ℝ3and the collapsible supercomplexXis not provided, we can expandKinto a convex ball of possibly quadratic complexity, which is known to be collapsible, resulting in nearly quadratic time algorithms.
登录
查看更多内容
超稀疏超稀疏器和更快的拉普拉斯系统求解器
DOI：
10.1137/1.9781611976465.33
发表时间：
2021
期刊：
SODA 2021
影响因子：
--
作者：
Jambulapati, Arun;Sidford, Aaron
通讯作者：
Sidford, Aaron
在近线性时间内求解 1-拉普拉斯算子：拓扑球的折叠和展开
影响因子：
8.3
作者：
Michael B. Cohen;Brittany Terese Fasy;G. Miller;A. Nayyeri;Richard Peng;N. Walkington
通讯作者：
N. Walkington
影响因子：
0.8
作者：
D. Chillingworth
通讯作者：
D. Chillingworth
影响因子：
0.8
作者：
D. Chillingworth
通讯作者：
D. Chillingworth
计算 R3 中单纯复形的同源群
DOI：
--
发表时间：
1998
期刊：
JACM
影响因子：
--
作者：
T. Dey;S. Guha
通讯作者：
S. Guha