Clear and Compress: Computing Persistent Homology in Chunks Book Section

Author(s): Bauer, Ulrich; Kerber, Michael; Reininghaus, Jan
Article/Chapter Title: Clear and Compress: Computing Persistent Homology in Chunks
Affiliation IST Austria
Abstract: We present a parallel algorithm for computing the persistent homology of a filtered chain complex. Our approach differs from the commonly used reduction algorithm by first computing persistence pairs within local chunks, then simplifying the unpaired columns, and finally applying standard reduction on the simplified matrix. The approach generalizes a technique by G√ľnther et al., which uses discrete Morse Theory to compute persistence; we derive the same worst-case complexity bound in a more general context. The algorithm employs several practical optimization techniques, which are of independent interest. Our sequential implementation of the algorithm is competitive with state-of-the-art methods, and we further improve the performance through parallel computation.
Book Title: Topological Methods in Data Analysis and Visualization III
ISBN: 978-3-319-04098-1
Publisher: Springer  
Date Published: 2014-01-01
Start Page: 103
End Page: 117
DOI: 10.1007/978-3-319-04099-8_7
Notes: The authors thank Chao Chen, Herbert Edelsbrunner, and Hubert Wagner for helpful discussions. This research is partially supported by the TOPOSYS project FP7-ICT-318493-STREP and the Max Planck Center for Visual Computing and Communication.
Open access: yes (repository)
IST Austria Authors
  1. Michael Kerber
    21 Kerber
  2. Ulrich Bauer
    12 Bauer
Related IST Austria Work