Fast Minimal Presentations of Bi-graded Persistence Modules

Michael Kerber, Alexander Rolle

Abstract

Multi-parameter persistent homology is a recent branch of topological data analysis. In this area, data sets are investigated through the lens of homology with respect to two or more scale parameters. The high computational cost of many algorithms calls for a preprocessing step to reduce the input size. In general, a minimal presentation is the smallest possible representation of a persistence module. Lesnick and Wright proposed recently an algorithm (the LW-algorithm) for computing minimal presentations based on matrix reduction. In this work, we propose, implement and benchmark several improvements over the LW-algorithm. Most notably, we propose the use of priority queues to avoid extensive scanning of the matrix columns, which constitutes the computational bottleneck in the LW-algorithm, and we combine their algorithm with ideas from the multi-parameter chunk algorithm by Fugacci and Kerber. Our extensive experiments show that our algorithm outperforms the LW-algorithm and computes the minimal presentation for data sets with millions of simplices within a few seconds. Our software is publicly available.

Introduction

Persistent homology is a cornerstone of Topological Data Analysis (TDA), allowing researchers to track how the "shape" of data—such as holes, voids, and connected components—evolves across different scales. While single-parameter persistence is well-understood and computationally efficient, many real-world scenarios require multi-parameter persistent homology. For instance, filtering a point cloud by both a distance scale and a density scale can better handle outliers.

However, multi-parameter persistence is algebraically complex. Unlike the single-parameter case, there is no simple "barcode" representation. Instead, researchers rely on a minimal presentation—the smallest possible matrix representation capturing all homological information. The previous state-of-the-art, the LW-algorithm, faced a significant computational bottleneck: it spent excessive time scanning large matrices to identify columns for updates, leading to quadratic time complexity that made large datasets intractable.

Algorithmic Improvements

To address these bottlenecks, we introduce mpfree, a high-performance tool implementing several key improvements:

  1. Priority Queues for Grid Traversal: Instead of exhaustive scans of the bi-graded grid, we use priority queues to predict which columns will be affected by previous operations. This eliminates the "empty work" that dominated prior implementations.
  2. Chunk Preprocessing: By integrating the "multi-parameter chunk algorithm," we perform lossless compression on the input cell complex. This removes redundant cells early, significantly reducing the workload for the main algorithm.
  3. Lazy Minimization: Redundant generators and relations are identified in bulk. This "lazy" approach avoids repeated matrix scans, transforming a previously quadratic step into a more efficient pass.
  4. Parallelization and Optimization: Key steps like reparameterization and chunking are parallelized using OpenMP. Furthermore, integration with the PHAT library allows for specialized matrix column representations (e.g., bit-trees) tailored to specific data structures.

Experimental Results

We benchmarked mpfree against the standard RIVET library across various datasets, including random convex hulls, function-Rips complexes, and triangular meshes.

Performance comparison between RIVET and a basic implementation of the LW-algorithm.

As shown in the initial benchmarks, even a basic implementation of the LW-algorithm (our "clone") offers substantial memory and time improvements over RIVET for larger datasets. However, the introduction of priority queues provides the most dramatic performance leap.

Impact of priority queue optimization on computation time and memory usage.

On the "Convex Hull" dataset (60k points), the original RIVET implementation required over 64GB of RAM and failed to complete within a reasonable timeframe. In contrast, our optimized implementation with priority queues and chunking finished in under 4 seconds using only 420MB of RAM. Empirical results suggest that while the theoretical worst-case remains higher, the algorithm scales near-linearly in practice, successfully processing complexes with over 8 million columns in approximately one minute.

Discussion and Future Work

The primary breakthrough of this work is shifting the computational focus from global search to local updates. By treating the bottleneck as a search problem rather than a linear algebra problem, we achieved orders-of-magnitude speedups. Preprocessing via the chunk algorithm also proved essential, as it quickly reduces the input size before more expensive operations begin.

Currently, mpfree is optimized for two-parameter (bi-graded) modules. Extending this to three or more parameters remains a challenge because the underlying algebraic structures are not necessarily free in higher dimensions. Future research will explore "lossy" approximations—simplifying modules while maintaining a bounded bottleneck distance—and the integration of mpfree into broader TDA pipelines for tasks like computing matching distances.

Summary updated

Abstract

Multi-parameter persistent homology is a recent branch of topological data analysis. In this area, data sets are investigated through the lens of homology with respect to two or more scale parameters. The high computational cost of many algorithms calls for a preprocessing step to reduce the input size. In general, a minimal presentation is the smallest possible representation of a persistence module. Lesnick and Wright proposed recently an algorithm (the LW-algorithm) for computing minimal presentations based on matrix reduction. In this work, we propose, implement and benchmark several improvements over the LW-algorithm. Most notably, we propose the use of priority queues to avoid extensive scanning of the matrix columns, which constitutes the computational bottleneck in the LW-algorithm, and we combine their algorithm with ideas from the multi-parameter chunk algorithm by Fugacci and Kerber. Our extensive experiments show that our algorithm outperforms the LW-algorithm and computes the minimal presentation for data sets with millions of simplices within a few seconds. Our software is publicly available.
BibTeX
@inproceedings{kerber2021fast,
  author = {Michael Kerber and Alexander Rolle},
  title = {{Fast Minimal Presentations of Bi-graded Persistence Modules}},
  booktitle = {ALENEX},
  year = {2021},
  doi = {10.1137/1.9781611976472.16},
}
Figure