Persistence algorithms, animated
Persistent homology is computed by reducing the boundary matrix \(D\) to a matrix \(R = DV\) whose non-zero columns have distinct lowest entries (pivots). The animations below run six reduction algorithms on the same \(8 \times 8\) matrix over \(\mathbb{Z}/2\), step by step: the lazy and exhaustive reductions, each processed column by column or row by row, and the fast column and row algorithms that run in matrix-multiplication time \(O(n^\omega)\).
The algorithms, and the numbering of algorithms and results in the animations, follow D. Morozov and P. Skraba, Persistent (Co)Homology in Matrix Multiplication Time, SoCG 2025 (LIPIcs 332, 68:1–68:16) · arXiv:2412.02591.
Erratum. The fast row algorithm (Algorithm 5) as printed in the SoCG 2025 proceedings is incorrect. The corrected algorithm is in the arXiv version, which the animation below follows.
Column algorithms
Row algorithms
Keys: Space play/pause, ←/→ previous/next step, −/+ slower/faster.
- non-zero entry
- pivot
- column being reduced
- column being added
- entry just changed