Clear and Compress: Computing Persistent Homology in Chunks

Ulrich Bauer, Michael Kerber, Jan Reininghaus

Abstract: We present a parallelizable algorithm for computing the persistent homology of a filtered chain complex. Our approach differs from the commonly used reduction algorithm by first computing persistence pairs within local chunks, then simplifying the unpaired columns, and finally applying standard reduction on the simplified matrix. The approach generalizes a technique by Günther et al., which uses discrete Morse Theory to compute persistence; we derive the same worst-case complexity bound in a more general context. The algorithm employs several practical optimization techniques which are of independent interest. Our sequential implementation of the algorithm is competitive with state-of-the-art methods, and we improve the performance through parallelized computation.

Introduction

Persistent homology is a cornerstone of computational topology, providing a robust framework for identifying topological features—such as holes, loops, and voids—that persist across multiple scales of a dataset. Despite its utility in topological data analysis (TDA), the standard reduction algorithm used to compute persistence pairs faces a significant hurdle: a worst-case cubic complexity ($O(n^3)$) relative to the number of simplices.

To mitigate this, researchers have historically relied on two primary optimizations: clearing and compression. Clearing skips the processing of columns that are mathematically guaranteed to become zero, while compression reduces the number of non-zero entries in the boundary matrix. However, these two techniques are notoriously difficult to implement simultaneously because they require conflicting processing orders. This paper introduces the "Clear and Compress" algorithm, a framework that successfully unifies these optimizations within a parallelizable "chunk-based" architecture.

The Chunk Algorithm: A Three-Stage Approach

The core innovation of this work is the Chunk Algorithm, which partitions the boundary matrix into consecutive segments or "chunks." This allows the algorithm to handle local and global topological features separately, bypassing the traditional ordering conflicts of clearing and compression.

1. Local Chunk Reduction

The boundary matrix is first divided into chunks that can be processed independently. During this stage, the algorithm applies the clearing optimization to identify "local" persistence pairs—features that are born and die within the same chunk or its immediate vicinity. Because each chunk is independent, this phase is highly amenable to parallelization, allowing for significant performance gains on multi-core processors.

2. Global Column Compression

Columns that remain unpaired after the local reduction are designated as "global" columns. These columns represent features that persist across multiple chunks. The algorithm identifies and eliminates "inactive" entries within these columns. This compression step simplifies the remaining workload and, like the first stage, can be executed in parallel.

3. Submatrix Reduction

The remaining unpaired and compressed columns form a significantly smaller "nested" submatrix. A final standard reduction (incorporating clearing) is performed on this submatrix to identify the remaining long-lived persistence pairs. While this final step is sequential, the preceding stages ensure that the submatrix is a fraction of the size of the original boundary matrix.

Experimental Evaluation

The authors evaluated the algorithm across five representative datasets to test its performance across different data structures and filtration types:

  • 3D Image Data (128³): Including "Smooth" (Fourier sum), "Noise" (uniform distribution), and "Mixed" structures.
  • Torus: An alpha shape filtration of 10,000 points sampled from a torus in $\mathbb{R}^3$.
  • Mumford: A 4-skeleton of a Rips filtration based on high-contrast image patches.

Key Insights and Results

The Locality of Features

A primary insight of the study is that in many real-world datasets, the vast majority of topological features are "local." For image-based datasets (Smooth, Noise, Mixed), the fraction of global columns was remarkably low, ranging from 0% to 9%. By resolving these local features early, the algorithm minimizes the work required in the final sequential reduction step.

Performance and Scalability

The parallel implementation demonstrated impressive scalability. Using a 12-core system, the algorithm achieved speedup factors between 3x and 11x compared to sequential versions. Even when run sequentially, the chunk algorithm remained competitive with state-of-the-art methods like the "twist" algorithm.

Limitations in High-Dimensional Complexes

The algorithm's effectiveness is somewhat dependent on the "locality" of the data. In the case of the Mumford Rips filtration, the global column ratio reached 82%. In such high-dimensional, highly interconnected complexes, the chunking strategy provides less benefit because the final sequential submatrix remains large.

Conclusion

The "Clear and Compress" algorithm represents a significant advancement in making persistent homology computations viable for large-scale data. By successfully combining clearing and compression through a parallelizable chunking strategy, the authors have provided a framework that is both theoretically sound and practically efficient. The implementation has been integrated into the PHAT (Persistent Homology Algorithms Toolbox), serving as a high-performance standard for the TDA community. Future work may involve optimizing the final submatrix reduction and exploring the impact of varying chunk sizes on different data topologies.

Summary updated

Abstract

We present a parallelizable algorithm for computing the persistent homology of a filtered chain complex. Our approach differs from the commonly used reduction algorithm by first computing persistence pairs within local chunks, then simplifying the unpaired columns, and finally applying standard reduction on the simplified matrix. The approach generalizes a technique by Günther et al., which uses discrete Morse Theory to compute persistence; we derive the same worst-case complexity bound in a more general context. The algorithm employs several practical optimization techniques which are of independent interest. Our sequential implementation of the algorithm is competitive with state-of-the-art methods, and we improve the performance through parallelized computation.
BibTeX
@inproceedings{bauer2014clear,
  author = {Ulrich Bauer and Michael Kerber and Jan Reininghaus},
  title = {{Clear and Compress: Computing Persistent Homology in Chunks}},
  booktitle = {Topological Methods in Data Analysis and Visualization},
  year = {2014},
  url = {https://openreview.net/forum?id=7kpa1TGy0b},
}
Figure