Skip to Main content Skip to Navigation
Conference papers

Strong Collapse for Persistence

Jean-Daniel Boissonnat 1 Siddharth Pritam 1 Divyansh Pareek 2
1 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We introduce a fast and memory ecient approach to compute the persistent homology (PH) of a sequence of simplicial complexes. The basic idea is to simplify the complexes of the input sequence by using strong collapses, as introduced by J. Barmak and E. Miniam [1], and to compute the PH of an induced sequence of reduced simplicial complexes that has the same PH as the initial one. Our approach has several salient features that distinguishes it from previous work. It is not limited to filtrations (i.e. sequences of nested simplicial subcomplexes) but works for other types of sequences like towers and zigzags. To strong collapse a simplicial complex, we only need to store the maximal simplices of the complex, not the full set of all its simplices, which saves a lot of space and time. Moreover, the complexes in the sequence can be strong collapsed independently and in parallel. As a result and as demonstrated by numerous experiments on publicly available data sets, our approach is extremely fast and memory ecient in practice. 1998 ACM Subject Classification Dummy classification-please refer to http://www.acm.org/ about/class/ccs98-html
Complete list of metadata

Cited literature [40 references]  Display  Hide  Download

https://hal.inria.fr/hal-01886165
Contributor : Jean-Daniel Boissonnat <>
Submitted on : Tuesday, October 2, 2018 - 4:04:10 PM
Last modification on : Thursday, November 8, 2018 - 1:04:23 AM
Long-term archiving on: : Thursday, January 3, 2019 - 3:23:22 PM

File

ESA_2018_Track_B_paper_21.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jean-Daniel Boissonnat, Siddharth Pritam, Divyansh Pareek. Strong Collapse for Persistence. ESA 2018 - 26th Annual European Symposium on Algorithms, Aug 2018, Helsinki, Finland. pp.67:1--67:13, ⟨10.4230/LIPIcs⟩. ⟨hal-01886165⟩

Share

Metrics

Record views

141

Files downloads

117