License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.34
URN: urn:nbn:de:0030-drops-160420
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16042/
Dey, Tamal K. ;
Kim, Woojin ;
Mémoli, Facundo
Computing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and Its Applications
Abstract
The notion of generalized rank invariant in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. Naturally, computing these rank invariants efficiently is a prelude to computing any of these derived structures efficiently. We show that the generalized rank over a finite interval I of a ?²-indexed persistence module M is equal to the generalized rank of the zigzag module that is induced on a certain path in I tracing mostly its boundary. Hence, we can compute the generalized rank over I by computing the barcode of the zigzag module obtained by restricting the bifiltration inducing M to that path. If the bifiltration and I have at most t simplices and points respectively, this computation takes O(t^ω) time where ω ∈ [2,2.373) is the exponent of matrix multiplication. Among others, we apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a module M, determine whether M is interval decomposable and, if so, compute all intervals supporting its summands.
BibTeX - Entry
@InProceedings{dey_et_al:LIPIcs.SoCG.2022.34,
author = {Dey, Tamal K. and Kim, Woojin and M\'{e}moli, Facundo},
title = {{Computing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and Its Applications}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {34:1--34:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-227-3},
ISSN = {1868-8969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16042},
URN = {urn:nbn:de:0030-drops-160420},
doi = {10.4230/LIPIcs.SoCG.2022.34},
annote = {Keywords: Multiparameter persistent homology, Zigzag persistent homology, Generalized Persistence Diagrams, M\"{o}bius inversion}
}
|
Keywords: |
|
Multiparameter persistent homology, Zigzag persistent homology, Generalized Persistence Diagrams, Möbius inversion |
|
Collection: |
|
38th International Symposium on Computational Geometry (SoCG 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.06.2022 |
