A spectral sequence for parallelized persistence
A spectral sequence for parallelized persistence
复制标题
用于并行持久化的谱序列
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Mikael Vejdemo
中科院分区：
文献类型：
--
作者：
D. Lipsky;P. Skraba;Mikael Vejdemo
采用分而治之的方法研究了大数据集的持久同源性计算问题。将总空间划分为独立但重叠的组件，我们能够限制计算任何部分的总内存驻留，同时不会大大降低总体复杂性。然后使用广义Mayer-Vietoris长精确序列的谱序列将局部计算的持久性信息从组件及其交点合并。
We approach the problem of the computation of persistent homology for large datasets by a divide-and-conquer strategy. Dividing the total space into separate but overlapping components, we are able to limit the total memory residency for any part of the computation, while not degrading the overall complexity much. Locally computed persistence information is then merged from the components and their intersections using a spectral sequence generalizing the Mayer-Vietoris long exact sequence.
We describe the Mayer-Vietoris spectral sequence and give details on how to compute with it. This allows us to merge local homological data into the global persistent homology. Furthermore, we detail how the classical topology constructions inherent in the spectral sequence adapt to a persistence perspective, as well as describe the techniques from computational commutative algebra necessary for this extension.
The resulting computational scheme suggests a parallelization scheme, and we discuss the communication steps involved in this scheme. Furthermore, the computational scheme can also serve as a guideline for which parts of the boundary matrix manipulation need to co-exist in primary memory at any given time allowing for stratified memory access in single-core computation. The spectral sequence viewpoint also provides easy proofs of a homology nerve lemma as well as a persistent homology nerve lemma. In addition, the algebraic tools we develop to approch persistent homology provide a purely algebraic formulation of kernel, image and cokernel persistence (D. Cohen-Steiner, H. Edelsbrunner, J. Harer, and D. Morozov. Persistent homology for kernels, images, and cokernels. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1011-1020. Society for Industrial and Applied Mathematics, 2009.)