Keeping it sparse: Computing Persistent Homology revisited
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916283979661312 |
|---|---|
| author | Bauer, Ulrich Masood, Talha Bin Giunti, Barbara Houry, Guillaume Kerber, Michael Rathod, Abhishek |
| author_facet | Bauer, Ulrich Masood, Talha Bin Giunti, Barbara Houry, Guillaume Kerber, Michael Rathod, Abhishek |
| contents | In this work, we study several variants of matrix reduction via Gaussian elimination that try to keep the reduced matrix sparse. The motivation comes from the growing field of topological data analysis where matrix reduction is the major subroutine to compute barcodes, the main invariant therein. We propose two novel variants of the standard algorithm, called swap and retrospective reductions. We test them on a large collection of data against other known variants to compare their efficiency, and we find that sometimes they provide a considerable speed-up. We also present novel output-sensitive bounds for the retrospective variant which better explain the discrepancy between the cubic worst-case complexity bound and the almost linear practical behavior of matrix reduction. Finally, we provide several constructions on which one of the variants performs strictly better than the others. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_09075 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Keeping it sparse: Computing Persistent Homology revisited Bauer, Ulrich Masood, Talha Bin Giunti, Barbara Houry, Guillaume Kerber, Michael Rathod, Abhishek Computational Geometry Algebraic Topology In this work, we study several variants of matrix reduction via Gaussian elimination that try to keep the reduced matrix sparse. The motivation comes from the growing field of topological data analysis where matrix reduction is the major subroutine to compute barcodes, the main invariant therein. We propose two novel variants of the standard algorithm, called swap and retrospective reductions. We test them on a large collection of data against other known variants to compare their efficiency, and we find that sometimes they provide a considerable speed-up. We also present novel output-sensitive bounds for the retrospective variant which better explain the discrepancy between the cubic worst-case complexity bound and the almost linear practical behavior of matrix reduction. Finally, we provide several constructions on which one of the variants performs strictly better than the others. |
| title | Keeping it sparse: Computing Persistent Homology revisited |
| topic | Computational Geometry Algebraic Topology |
| url | https://arxiv.org/abs/2211.09075 |