Discrete Morse Theory for Computing Zigzag Persistence
Discrete Morse Theory for Computing Zigzag Persistence
复制标题
用于计算之字形持久性的离散莫尔斯理论
DOI：
10.1007/978-3-030-24766-9_39
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Hannah Schreiber
中科院分区：
文献类型：
--
作者：
Clément Maria;Hannah Schreiber
我们介绍了一个理论和计算框架，使用离散莫尔斯理论作为有效的预处理，以计算之字形持久同调。从络合物的锯齿形过滤出发，引入了锯齿形莫尔斯过滤，其络合物是原络合物的莫尔斯还原，并证明了它们具有相同的持久同源性。这种锯齿形莫尔斯滤波推广了Mischaikow和Nanda的滤波莫尔斯复合体（离散计算学报50(2):330-353,2013），定义为标准持久性。锯齿形莫尔斯滤波中的映射是锯齿形持久化中标准的前向和后向内含，也是引起莫尔斯复合体边界算符发生重大变化的一种新型映射。我们详细研究了最后一个映射，并设计了在计算之字形持久化时在复杂级别和同调矩阵级别计算更新的算法。我们的构造的关键点是，它不需要任何输入过滤的过去和未来地图的知识。我们推导了一种计算过滤之字形持久性的算法，该算法主要取决于复合物的关键细胞的数量，并通过实验表明，它在实践中表现得更好。
We introduce a theoretical and computational framework to use discrete Morse theory as an efficient preprocessing in order to compute zigzag persistent homology. From a zigzag filtration of complexes, we introduce azigzag Morse filtrationwhose complexesare Morse reductions of the original complexes, and we prove that they both have same persistent homology. This zigzag Morse filtration generalizes thefiltered Morse complexof Mischaikow and Nanda Mischaikow and Nanda (Discrete Comput Geom 50(2):330–353, 2013), defined for standard persistence. The maps in the zigzag Morse filtration are forward and backward inclusions, as is standard in zigzag persistence, as well as a new type of map inducing non trivial changes in the boundary operator of the Morse complex. We study in details this last map, and design algorithms to compute the update both at the complex level and at the homology matrix level when computing zigzag persistence. The key point of our construction is that it does not require any knowledge of past and future maps of the input filtration. We deduce an algorithm to compute the zigzag persistence of a filtration that depends mostly on the number of critical cells of the complexes, and show experimentally that it performs better in practice.
DOI：
10.1109/tvcg.2018.2864848
发表时间：
2019-01
影响因子：
5.2
作者：
A. Gyulassy;P. Bremer;Valerio Pascucci
通讯作者：
A. Gyulassy;P. Bremer;Valerio Pascucci