Source-linked AI summary
Ripser: efficient computation of Vietoris-Rips persistence barcodes
Ulrich Bauer
TL;DR
Computing Vietoris–Rips persistence barcodes is limited by the construction and storage of filtration matrices. Ripser uses implicit filtration and coboundary representations together with matrix-reduction and apparent-pair optimizations, and reports substantial improvements in time and memory usage over previous software. The paper also identifies scope boundaries involving nonzero-persistence apparent pairs and coefficient-field dependence of emergent pairs.
Problem
Constructing the filtration boundary matrix can become the bottleneck in Vietoris–Rips barcode computation, motivating methods that avoid constructing and storing it as a whole.
Method
Ripser represents the filtration and coboundary operator algorithmically, uses implicit reduction, and applies clearing, cohomology, emergent-pair, and apparent-pair shortcuts.
Results
Ripser reports substantial improvements over previous software in both time and memory usage.
Takeaways & Limitations
Apparent pairs provide a locally identifiable persistence-pair construction that is also presented as a discrete-gradient method of independent interest.
Takeaways & Limitations
The paper notes that apparent pairs can have nonzero persistence, while emergent-pair status depends on the coefficient field.
Abstract
from arXiv · showhide
We present an algorithm for the computation of Vietoris-Rips persistence barcodes and describe its implementation in the software Ripser. The method relies on implicit representations of the coboundary operator and the filtration order of the simplices, avoiding the explicit construction and storage of the filtration coboundary matrix. Moreover, it makes use of apparent pairs, a simple but powerful method for constructing a discrete gradient field from a total order on the simplices of a simplicial complex, which is also of independent interest. Our implementation shows substantial improvements over previous software both in time and memory usage.
1 Introduction
Ripser targets the filtration-matrix bottleneck in Vietoris–Rips persistence computation through implicit representations and pair-based shortcuts. Its implementation combines memory-saving strategies with optimizations that can also improve runtime.
- Constructing the filtration boundary matrix often becomes the bottleneck in computing Vietoris–Rips barcodes.
- Ripser represents the coboundary operator and filtration order algorithmically, recomputing coboundaries and comparing simplices when needed instead of storing them explicitly.
- The implementation uses four key matrix-reduction optimizations, including clearing and cohomology, with ideas applicable beyond Vietoris–Rips filtrations.
- The method avoids storing the full reduced matrix, retaining a smaller reduction matrix and pivot information needed for column operations.
- Apparent pairs are identified locally from simplex facets and cofacets, while emergent pairs are detected during reduction to shorten coboundary-column construction.
- Apparent pairs are presented as a discrete-gradient construction of independent interest and as a method expected to matter for discrete Morse theory and persistent homology.
2 Preliminaries
The preliminaries define simplicial complexes, filtrations, Vietoris–Rips constructions, and persistence barcodes, then explain how refinements and simplex indexing support computation. They also introduce discrete Morse-theoretic terminology used for apparent pairs.
- A simplicial complex is a collection of simplices closed under taking faces, and a filtration is an ordered sequence of nested subcomplexes.
- The Vietoris–Rips filtration varies a scale parameter on a finite metric space, producing complexes whose simplices are determined by bounded diameters.
- The real-indexed Vietoris–Rips filtration can be condensed and then refined to an essential simplexwise filtration for persistent-homology computation.
- Discrete Morse theory represents gradient fields through paired facets and cofacets, providing terminology for the paper’s simplex-pair constructions.
- Persistent homology decomposes into interval modules, whose interval collection forms the persistence barcode with birth, death, and essential indices.
- A simplexwise refinement preserves the barcode after reindexing intervals according to the refinement map, while zero-persistence intervals may disappear under non-surjective reindexing.
- The combinatorial number system indexes simplices of the full simplex and Vietoris–Rips filtration by natural numbers, with binary search enabling vertex recovery.
3 Computation
Ripser accelerates persistent-homology computation by combining matrix-reduction optimizations with implicit coboundary and reduction-matrix representations. Clearing, cohomology, and apparent-pair shortcuts reduce stored or processed columns, while apparent pairs also connect persistence computation to discrete Morse theory.
- 3 Computation: Persistent homology is computed by reducing a filtration boundary matrix, with reduced columns and pivots determining persistence pairs and essential indices.The reduction can target the full filtration or individual boundary maps, and may retain the reduction matrix for representative-cycle information.
- 3.2 Clearing inessential birth columns: Clearing sets a column to zero when its index is the pivot of another reduced column, avoiding reductions for inessential birth indices.The optimization exploits the fact that those columns do not contribute to the persistence pairs identified by the reduction.
- 3.3 Persistent Cohomology: Combining clearing with cohomology leaves 1 161 472 columns for p = 2 and n = 192, including 1 161 471 death columns and one birth column.The paper reports that this combination drastically reduces column operations in practice compared with the standard reduction.
- 3.5 Apparent pairs: Apparent pairs are persistence pairs identifiable from local facet and cofacet conditions, and their collection forms a discrete gradient field.Theorem 3.10 states that, under distinct pairwise distances, they are precisely the zero-persistence pairs in dimension 1 of a simplexwise Vietoris–Rips refinement.
- 3.5 Apparent pairs: Apparent and emergent shortcuts identify pairs without enumerating all cofacets, avoiding full coboundary construction; Ripser also omits column indices belonging to zero-persistence apparent pairs.These shortcuts reduce both the computation and the memory needed for the reduction.
4 Implementation
Ripser implements persistence computation with compact representations and specialized enumeration routines for simplices, cofacets, and facets. Version 1.2 further avoids assembling columns associated with zero-persistence apparent pairs and supports prime-field coefficients.
- Input and data structures: Ripser is implemented in C++ and accepts finite metric spaces represented by distance matrices or Euclidean point lists.Dense matrices use compressed triangular storage, while sparse matrices use adjacency lists below a threshold.
- Input and data structures: Vertices and simplices use natural-number indices, with simplices encoded by the combinatorial number system and simplex dimensions passed separately.The implementation uses 64-bit signed integers for both vertex and simplex indices.
- Simplex indexing: Binary search and precomputed binomial coefficients enable efficient recovery and enumeration of simplex vertices from combinatorial indices.These operations are implemented through get_max_vertex, get_simplex_vertices, and binomial_coeff_table.
- Enumerating simplices: Cofacets and facets are enumerated directly in reverse or forward colexicographic order while maintaining partial sums for index updates.Dense and sparse distance matrices use different cofacet-enumeration procedures; coboundary coefficients are assigned as (−1)^k.
- Apparent-pair optimization: Version 1.2 assembles only column indices not belonging to zero-persistence apparent pairs, reducing both memory usage and computation time.The implementation checks apparent cofacets and facets using lexicographic extremal simplices with matching diameter.
- Coefficients: Ripser supports persistent homology over any prime field F_p with prime p < 2^16.Prime-field support is controlled by a compiler flag, and coefficients use a 16-bit unsigned integer representation.
5 Experiments
Experiments compare Ripser’s optimization variants and examine how frequently apparent and emergent pairs occur in typical data sets. The results show that these shortcuts identify a large portion of persistence pairs, while recreating discarded reduced columns adds negligible runtime cost.
- Apparent and emergent pairs: A large portion of persistence pairs in typical data sets are apparent or emergent zero-persistence pairs identifiable through shortcuts.In dimension 1, every zero pair is apparent and emergent; higher dimensions also contain non-emergent zero-persistence pairs and some non-zero emergent pairs.
- Optimization experiments: Table 3 compares running times as Ripser successively enables implicit reduction, reduced-matrix discarding, emergent-pair shortcuts, and apparent-pair skipping.All variants also use clearing and compute cohomology.
- Optimization experiments: The extra cost of recreating discarded reduced columns is negligible in practice, because implicit and explicit reduction with stored reduced matrices have similar timings.The comparison concerns explicit reduction and implicit reduction variants that store the reduced matrix.
- Apparent and emergent pairs: Table 2 counts zero, emergent, shortcut, non-emergent, non-shortcut, non-apparent, and total persistence pairs across data sets and dimensions.A shortcut pair is both a zero pair and an emergent pair, and therefore also an apparent pair.