2026-09-05T11:58:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25816 2026-06-23T12:58:55Z ddc:004 open_access

Fast Free Resolutions of Bifiltered Chain Complexes Bauer, Ulrich Dey, Tamal K. Kerber, Michael Russold, Florian Söls, Matthias Topological Data Analysis Multi-Parameter Persistence Multi-Critical Bifiltrations 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ulrich Bauer and Tamal K. Dey and Michael Kerber and Florian Russold and Matthias Söls 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.10 urn:nbn:de:0030-drops-258161 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.10 eng https://creativecommons.org/licenses/by/4.0/legalcode