Fast free resolutions of bifiltered chain complexes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910064445489152 |
|---|---|
| author | Bauer, Ulrich Dey, Tamal K. Kerber, Michael Russold, Florian Söls, Matthias |
| author_facet | Bauer, Ulrich Dey, Tamal K. Kerber, Michael Russold, Florian Söls, Matthias |
| contents | In a $k$-critical bifiltration, every simplex enters along a staircase with at most $k$ steps. Examples with $k>1$ include degree-Rips bifiltrations and models of the multicover bifiltration. We consider the problem of converting a $k$-critical bifiltration into a $1$-critical (i.e. free) chain complex with equivalent homology. This is known as computing a free resolution of the underlying chain complex and is a first step toward post-processing such bifiltrations.
We present two algorithms. The first one computes free resolutions corresponding to path graphs and assembles them to a chain complex by computing additional maps. The simple combinatorial structure of path graphs leads to good performance in practice, as demonstrated by extensive experiments. However, its worst-case bound is quadratic in the input size because long paths might yield dense boundary matrices in the output. Our second algorithm replaces the simplex-wise path graphs with ones that maintain short paths which leads to almost linear runtime and output size.
We demonstrate that pre-computing a free resolution speeds up the task of computing a minimal presentation of the homology of a $k$-critical bifiltration in a fixed dimension. Furthermore, our findings show that a chain complex that is minimal in terms of generators can be asymptotically larger than the non-minimal output complex of our second algorithm in terms of description size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_08652 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast free resolutions of bifiltered chain complexes Bauer, Ulrich Dey, Tamal K. Kerber, Michael Russold, Florian Söls, Matthias Algebraic Topology In a $k$-critical bifiltration, every simplex enters along a staircase with at most $k$ steps. Examples with $k>1$ include degree-Rips bifiltrations and models of the multicover bifiltration. We consider the problem of converting a $k$-critical bifiltration into a $1$-critical (i.e. free) chain complex with equivalent homology. This is known as computing a free resolution of the underlying chain complex and is a first step toward post-processing such bifiltrations. We present two algorithms. The first one computes free resolutions corresponding to path graphs and assembles them to a chain complex by computing additional maps. The simple combinatorial structure of path graphs leads to good performance in practice, as demonstrated by extensive experiments. However, its worst-case bound is quadratic in the input size because long paths might yield dense boundary matrices in the output. Our second algorithm replaces the simplex-wise path graphs with ones that maintain short paths which leads to almost linear runtime and output size. We demonstrate that pre-computing a free resolution speeds up the task of computing a minimal presentation of the homology of a $k$-critical bifiltration in a fixed dimension. Furthermore, our findings show that a chain complex that is minimal in terms of generators can be asymptotically larger than the non-minimal output complex of our second algorithm in terms of description size. |
| title | Fast free resolutions of bifiltered chain complexes |
| topic | Algebraic Topology |
| url | https://arxiv.org/abs/2512.08652 |