| | |
| | |
Stat |
Members: 3645 Articles: 2'501'711 Articles rated: 2609
20 April 2024 |
|
| | | |
|
Article overview
| |
|
A spectral sequence for parallelized persistence | David Lipsky
; Primoz Skraba
; Mikael Vejdemo-Johansson
; | Date: |
6 Dec 2011 | Abstract: | 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.) | Source: | arXiv, 1112.1245 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |