DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2026.10

Fast Free Resolutions of Bifiltered Chain Complexes

Authors: Ulrich Bauer, Tamal K. Dey, Michael Kerber, Florian Russold, and Matthias Söls

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

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.

Cite as

Ulrich Bauer, Tamal K. Dey, Michael Kerber, Florian Russold, and Matthias Söls. Fast Free Resolutions of Bifiltered Chain Complexes. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.SoCG.2026.10,
  author =	{Bauer, Ulrich and Dey, Tamal K. and Kerber, Michael and Russold, Florian and S\"{o}ls, Matthias},
  title =	{{Fast Free Resolutions of Bifiltered Chain Complexes}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.10},
  URN =		{urn:nbn:de:0030-drops-258161},
  doi =		{10.4230/LIPIcs.SoCG.2026.10},
  annote =	{Keywords: Topological Data Analysis, Multi-Parameter Persistence, Multi-Critical Bifiltrations}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2023.45

The Localized Union-Of-Balls Bifiltration

Authors: Michael Kerber and Matthias Söls

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract

We propose an extension of the classical union-of-balls filtration of persistent homology: fixing a point q, we focus our attention to a ball centered at q whose radius is controlled by a second scale parameter. We discuss an absolute variant, where the union is just restricted to the q-ball, and a relative variant where the homology of the q-ball relative to its boundary is considered. Interestingly, these natural constructions lead to bifiltered simplicial complexes which are not k-critical for any finite k. Nevertheless, we demonstrate that these bifiltrations can be computed exactly and efficiently, and we provide a prototypical implementation using the CGAL library. We also argue that some of the recent algorithmic advances for 2-parameter persistence (which usually assume k-criticality for some finite k) carry over to the ∞-critical case.

Cite as

Michael Kerber and Matthias Söls. The Localized Union-Of-Balls Bifiltration. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kerber_et_al:LIPIcs.SoCG.2023.45,
  author =	{Kerber, Michael and S\"{o}ls, Matthias},
  title =	{{The Localized Union-Of-Balls Bifiltration}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.45},
  URN =		{urn:nbn:de:0030-drops-178953},
  doi =		{10.4230/LIPIcs.SoCG.2023.45},
  annote =	{Keywords: Topological Data Analysis, Multi-Parameter Persistence, Persistent Local Homology}
}

Search Results

Documents authored by Söls, Matthias

Fast Free Resolutions of Bifiltered Chain Complexes

Abstract

Cite as

The Localized Union-Of-Balls Bifiltration

Abstract

Cite as

Thanks for your feedback!

Could not send message