Computer Science – Computational Geometry
Scientific paper
2011-12-06
Computer Science
Computational Geometry
15 pages, 10 figures, submitted to the ACM Symposium on Computational Geometry
Scientific paper
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.)
Lipsky David
Skraba Primoz
Vejdemo-Johansson Mikael
No associations
LandOfFree
A spectral sequence for parallelized persistence does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A spectral sequence for parallelized persistence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A spectral sequence for parallelized persistence will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-380977