Skip to Main content Skip to Navigation
Book sections

Discrete Morse Theory for Computing Zigzag Persistence

Clément Maria 1 Hannah Schreiber 2
1 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We introduce a theoretical and computational framework to use discrete Morse theory as an efficient preprocessing in order to compute zigzag persistent homology. From a zigzag filtration of complexes $(K_i)$, we introduce a {\em zigzag Morse filtration} whose complexes $(A_i)$ are Morse reductions of the original complexes $(K_i)$, and we prove that they both have same persistent homology. This zigzag Morse filtration generalizes the {\em filtered Morse complex} of Mischaikow and Nanda~\cite{MischaikowN13}, defined for standard persistence. The maps in the zigzag Morse filtration are forward and backward inclusions, as is standard in zigzag persistence, as well as a new type of map inducing non trivial changes in the boundary operator of the Morse complex. We study in details this last map, and design algorithms to compute the update both at the complex level and at the homology matrix level when computing zigzag persistence. We deduce an algorithm to compute the zigzag persistence of a filtration that depends mostly on the number of critical cells of the complexes, and show experimentally that it performs better in practice.
Complete list of metadatas

Cited literature [47 references]  Display  Hide  Download

https://hal.inria.fr/hal-01971682
Contributor : Clément Maria <>
Submitted on : Monday, January 6, 2020 - 6:00:02 PM
Last modification on : Monday, January 13, 2020 - 2:06:54 PM
Long-term archiving on: : Wednesday, April 8, 2020 - 12:21:46 AM

File

main.pdf
Files produced by the author(s)

Identifiers

Citation

Clément Maria, Hannah Schreiber. Discrete Morse Theory for Computing Zigzag Persistence. Friggstad, Zachary; Sack, Jörg-Rüdiger; Salavatipour, Mohammad R. Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings, Springer, pp.538-552, 2019, ⟨10.1007/978-3-030-24766-9_39⟩. ⟨hal-01971682v2⟩

Share

Metrics

Record views

57

Files downloads

222