# Keeping it sparse: Computing Persistent Homology revisited

arXiv: https://arxiv.org/abs/2211.09075 · HTML: https://mlsanity.com/paper/2211.09075/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Nov 2022.

## Built on by (most cited first, 6 of 6)

- [On the Expressivity of Persistent Homology in Graph Learning](https://mlsanity.com/paper/2302.09826/) (2023)
- [Stable Vectorization of Multiparameter Persistent Homology using Signed Barcodes as Measures](https://mlsanity.com/paper/2306.03801/) (2023)
- [Graphcode: Learning from multiparameter persistent homology using graph neural networks](https://mlsanity.com/paper/2405.14302/) (2024)
- [Topological Parallax: A Geometric Specification for Deep Perception Models](https://mlsanity.com/paper/2306.11835/) (2023)
- [Unreduced Persistence Diagrams for Topological Machine Learning](https://mlsanity.com/paper/2507.07156/) (2025)
- [TopoPrune: Robust Data Pruning via Unified Latent Space Topology](https://mlsanity.com/paper/2602.02739/) (2026)

## Abstract (arXiv)

In this work, we study several variants of matrix reduction via Gaussian elimination that try to keep the reduced matrix sparse. The motivation comes from the growing field of topological data analysis where matrix reduction is the major subroutine to compute barcodes, the main invariant therein. We propose two novel variants of the standard algorithm, called swap and retrospective reductions. We test them on a large collection of data against other known variants to compare their efficiency, and we find that sometimes they provide a considerable speed-up. We also present novel output-sensitive bounds for the retrospective variant which better explain the discrepancy between the cubic worst-case complexity bound and the almost linear practical behavior of matrix reduction. Finally, we provide several constructions on which one of the variants performs strictly better than the others.