CoChat
Sign Up
PreprintCited by 22Topological and Geometric Data AnalysisHomotopy and Cohomology in Algebraic TopologyDigital Image Processing Techniques

A spectral sequence for parallelized persistence

Open access
Lipsky, David, Skraba, Primoz, Vejdemo-Johansson, Mikael·2011·arXiv
DOI 10.48550/arxiv.1112.1245arXiv 1112.1245
Open this paper in CoChat — free accountOpen PDF

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.)

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1112.1245

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The Mayer-Vietoris procedure has been adapted to the persistent homology situation.

    “This procedure has been adapted to the persistent homology situation in Lipsky, Skraba and Vejdemo-Johansson (2011).”

    From Topological pattern recognition for point cloud data (2014) · cites this paper as Lipsky, Skraba and Vejdemo-Johansson (2011)

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

No citation lists for this paper

No citation lists for this paper yet — checked again daily.

References 28 · Cited by 22

Research works printed but not linked: 19

  1. [1][1] R. Bott and L. Tu. Differential forms in algebraic topology , volume 82. Springer, 1982. -
  2. [2][2] K. Brown. Cohomology of groups , volume 87 of Graduate Texts in Mathematics . Springer, 1982. -
  3. [4][4] F. Chazal and S. Y. Oudot. Towards persistence-based reconstruction in euclidean spaces. In Proc. 24th ACM Sympos. Comput. Geom. , pages 232-241, 2008. -
  4. [5][5] C. Chen and M. Kerber. An output-sensitive algorithm for persistent homology. In Proceedings of the 27th annual symposium on Computational geometry , 2011. -
  5. [7][7] 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. -
  6. [8][8] D. Cohen-Steiner, H. Edelsbrunner, and D. Morozov. Vines and vineyards by updating persistence in linear time. In Proceedings of the twenty-second annual symposium on Computational geometry , SCG '06, pages 119-126, New York, NY, USA, 2006. ACM. -
  7. [9][9] A. L. D. Attali and D. Salinas. Efficient data structure for representing and simplifying simplicial complexes in high dimension. In Proc. 27th ACM Sympos. Comput. Geom. , 2011. -
  8. [11][11] P. Dlotko, T. Kaczynski, M. Mrozek, and T. Wanner. Coreduction homology algorithm for regular cw-complexes. Discrete and Computational Geometry , 46(2):361-388, 2011. -
  9. [12][12] H. Edelsbrunner and J. Harer. Computational Topology: an Introduction . AMS Press, 2009. -
  10. [14][14] D. Eisenbud. Commutative algebra with a view toward algebraic geometry , volume 150. Springer, 1995. -
  11. [17][17] S. Harker, K. Mischaikow, M. Mrozek, V. Nanda, H. Wagner, M. Juda, and P. Dlotko. The efficiency of a homology algorithm based on discrete morse theory and coreductions. In 3rd International Workshop on Computational Topology in Image Context , November 2010. -
  12. [19][19] A. Hatcher. Algebraic topology . Cambridge University Press, 2005. -
  13. [21][21] J. McCleary. A user's guide to spectral sequences , volume 58. Cambridge Univ Pr, 2001. -
  14. [22][22] N. Milosavljevic, D. Morozov, P. Skraba, et al. Zigzag persistent homology in matrix multiplication time. In Annual Symposium on Computational Geometry , pages 247-256, 2009. -
  15. [26][26] A. Muhammad and A. Jadbabaie. Distributed computation of homology groups by gossip. In American Control Conference, ACC 2007 , 2007. -
  16. [27][27] C. Sims. Abstract algebra: a computational approach . John Wiley & Sons, Inc., 1984. -
  17. [28][28] A. Zomorodian. Topology for computing . Cambridge Univ Pr, 2005. -
  18. [29][29] A. Zomorodian. Fast construction of the vietoris-rips complex. Computers & Graphics , 34(3):263-271, 2010. -
  19. [32][32] A. Zomorodian and G. Carlsson. Localized homology. In Shape Modeling and Applications, 2007. SMI'07. IEEE International Conference on , pages 189-198. IEEE, 2007. Figure 7. The basic reduction: As in [8], we reduce the matrix R left to right, always choosing the lowest possible pivot with shaded areas representing non-zero entries. In contrast with [8], we represent each dimension separately, so the matrices are not upper triangular. As we reduce R , we perform the same operations on C . At the end, we perform a permutation to put the columns with pivots on the left (this is not done in practice). These represent the boundary basis and the corresponding columns in C are the preboundary basis. The columns in C corresponding to the empty columns in R are the cycle basis. <!-- image -->

Authors
Lipsky, D., Skraba, P., & Vejdemo-Johansson, M.
Affiliations
University of Pennsylvania (US)
Venue
arXiv
Publisher
arXiv
Published
2011
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1112.1245
arXiv
1112.1245
OpenAlex
W2269879476
Cited by
22
References
28
Citations by year
2023: 2 · 2021: 2 · 2019: 2 · 2017: 2 · 2016: 3 · 2015: 1 · 2014: 4 · 2013: 4 · 2012: 2
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Topological and Geometric Data Analysis
  • Physical Sciences › Mathematics › Mathematical Physics › Homotopy and Cohomology in Algebraic Topology
  • Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Digital Image Processing Techniques
Keywords
persistent homology, divide-and-conquer, memory-efficient computation, boundary matrix, computational commutative algebra, parallel communication

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review