Source-linked AI summary
Matroid Filtrations and Computational Persistent Homology
Gregory Henselman, Robert Ghrist
TL;DR
The report seeks efficient computational tools for homological algebra over a field, with particular emphasis on persistent homology of filtered complexes. The approach combines matroid theory, discrete Morse simplification, and classical matrix factorization to compute persistent homology while avoiding storage of the full boundary operator. At the time of writing, the largest complex whose homology was computed had a 2-skeleton with over 160 billion simplices; all Table 2 instances computed persistent H1.
Problem
The report seeks efficient computational tools for homological algebra over a field, with particular emphasis on persistent homology of filtered complexes.
Source: §1 · p. 1Method
The approach combines matroid theory, discrete Morse simplification, and classical matrix factorization to compute persistent homology while avoiding storage of the full boundary operator.
Source: §1 · p. 1Results
At the time of writing, the largest complex whose homology was computed had a 2-skeleton with over 160 billion simplices; all Table 2 instances computed persistent H1.
Source: §7 · p. 12Takeaways & Limitations
The method can compute persistent H1 on very large complexes, while acyclic compression has limited reach on difficult fixed complexes with many higher-dimensional simplices and relatively large homology.
Source: §7 · p. 12On matching and chessboard complexes with few vertices, many higher-dimensional simplices, and relatively large homology, acyclic compression can only do so much.
Source: §7 · p. 12
Abstract
from arXiv · showhide
This technical report introduces a novel approach to efficient computation in homological algebra over fields, with particular emphasis on computing the persistent homology of a filtered topological cell complex. The algorithms here presented rely on a novel relationship between discrete Morse theory, matroid theory, and classical matrix factorizations. We provide background, detail the algorithms, and benchmark the software implementation in the Eirene package.
1. INTRODUCTION
The report develops efficient algorithms for homological computations, focusing on persistent homology as an application. It combines matroid theory, discrete Morse theory, and matrix factorization to reduce computation and memory use while retaining access to representative homology generators.
1. INTRODUCTION
- Persistent homology is framed as a particular instance of constructible cosheaf homology over the real line, an application relevant to topological data analysis.Source: §1 · p. 1
- The approach combines matroid theory, discrete Morse theory, and classical matrix factorization to compute persistent homology quickly and memory-efficiently.It also targets cosheaf homology and sheaf cohomology in the cellular setting.Source: §1 · p. 1
- Discrete Morse simplification preserves homology while helping avoid construction and storage of the full boundary operator.This is the stated route to improved memory performance.Source: §1 · p. 1
- Classical matrix factorization theorems support efficient computation and recovery of representative homology generators as chains in the original complex.Source: §1 · p. 1
2. BACKGROUND
The background introduces matroids as independence systems and develops the operations and optimization language used in the algorithms. It then defines weight-compatible matrix structure needed in later sections.
2. BACKGROUND
- The report assumes matroids are finitary and of finite rank for economy of exposition.Source: §2 · p. 2
- A matroid is specified by a ground set and an independence system satisfying heredity and exchange; maximal independent sets are bases and minimal dependent sets are circuits.Source: §2 · p. 2
- Linear matroids encode linear independence, with rank corresponding to the dimension of the span in the represented vector space.Source: §2 · pp. 2–3
- Matroid deletion and contraction produce minors, with contraction reducing rank by the rank of the contracted set.Source: §2 · p. 3
- A k-linear representation maps ground-set elements to vectors so that matroid independence matches linear independence.A basis-standard representation sends the basis vectors to standard unit vectors.Source: §2 · p. 3
- For matroids, the greedy algorithm finds a maximum-weight independent set, and negating weights gives a method for finding minimal bases.Source: §2 · pp. 3–4
- An f-upper-triangular matrix has nonzero entries only where the row weight is no greater than the column weight; products and inverses preserve this property.Source: §2 · p. 4
- For flat weights, triangularity of a basis-exchange matrix characterizes whether a basis is weight-minimal relative to a minimal basis.Source: §2 · p. 4
3. MODULAR FILTRATIONS
The section introduces modular filtrations to connect linear persistence with matroid optimization. It characterizes when two filtrations admit a jointly minimal basis and gives a criterion in terms of basis intersections.
3. MODULAR FILTRATIONS
- A pair of filtrations is modular when the rank identity for each pair of filtration flats holds.Source: §3 · p. 5
- Two filtrations are modular if and only if there is a basis minimal for both characteristic-function weights, equivalently one satisfying the stated intersection-basis condition.Source: §3 · p. 5
- The excerpt lists modularity of (F,G) and a basis minimal with respect to both χF and χG as conditions, then begins a third basis condition ending “for all i, j.”Source: §3 · p. 5
- The constructive argument builds a jointly minimal basis by extending bases of successive filtration intersections.Source: §3 · pp. 5–6
- Lemma 6 provides an efficient way to check independence over large families of intersections.Source: §3 · p. 5
4. LINEAR FILTRATIONS
Linear filtrations admit a basis that simultaneously captures every intersection of the two filtrations. The section develops matrix-reduction procedures for constructing such minimal bases.
4. LINEAR FILTRATIONS
- For linear filtrations, a basis exists whose elements in each Fi ∩ Gj span that intersection.This follows from the corresponding matroid result because linear filtrations are matroid-theoretic filtrations.Source: §4 · p. 6
- The construction starts from an F-minimal basis, a set containing a χG-minimal basis, and oracles for the two orders, then combines vectors from G.If needed, the problem can be transferred through an F-standard representation and mapped back.Source: §4 · p. 6
- The matrix construction uses P as the Pareto-optimal frontier of the nonzero support of A under the chosen orders.The associated L and R transformations are triangular in their respective filtration orders.Source: §4 · p. 7
- Matrix reduction stops within at most r iterations, and the columns of L^-1 form an (F,G)-minimal basis.The accumulated L and R products are χF-upper-triangular and χG-lower-triangular, respectively.Source: §4 · p. 7
- The light matrix-reduction variant omits R from the calculation of L^-1 and adjusts its stopping criterion because LA may be denser than LAR.Its iteration condition is based on whether |P(At)| has reached r.Source: §4 · pp. 7–8
5. HOMOLOGICAL PERSISTENCE
The section connects filtrations of chain complexes to homology and persistence modules, then applies minimal-basis computation to cycle spaces. Its algorithm terminates with a minimal basis of the cycle space.
5. HOMOLOGICAL PERSISTENCE
- A nested sequence of chain complexes induces a persistence module, and the blue bars in Figure 2 correspond exactly to the barcode of the induced filtrations.The module is a graded k[t]-module whose t-action comes from the induced maps on homology.Source: §5 · p. 8, Figure 2 · p. 9
- For the induced modular pair on the cycle space, the non-nullhomologous classes of a (χF,χG)-minimal cycle basis freely generate Hn(C).Each cycle maps to its homology class at the first filtration index containing it.Source: §5 · p. 8
- Algorithm 4 takes filtration-minimal bases for chain groups, a linear order, and boundary-operator matrices as input.The input bases are indexed by dimensions, and the matrices represent the boundary operators with respect to those bases.Source: §5 · pp. 8–9
- Algorithm 4 terminates, and its output columns form a (χF,χG)-minimal basis of Zn.The cited result identifies the output using Pn+1 at the terminating iteration.Source: §5 · p. 9
6. ACYCLIC RELATIONS
Sparse matrix products can be costly, so the section uses acyclic relations to identify matchings that can be included in a compatible order. These matchings support chain reduction while avoiding construction of portions of large boundary operators and, in some cases, the underlying complex.
6. ACYCLIC RELATIONS
- Acyclic matchings provide a way to include known pairs in P1 n and engineer an order that can reduce the iterations needed for sparse chain reduction.Sparse representation can make matrix products disproportionately costly, and Algorithm 4 stops when |P1 n| = rank An.Source: §6 · p. 10
- Every acyclic f-relation extends to an f-linear order, and an acyclic matching is χF-acyclic exactly when χF has equal values on each matched pair.These properties connect relation acyclicity and filtration values to choosing compatible orders and matchings.Source: §6 · pp. 10–11
- A matching V is included in the union of the P(An,<) sets when the opposite order linearizes RV; f-acyclic matchings can therefore be included for some f-linear order.This provides a route from acyclic matchings to sets usable by the reduction algorithm.Source: §6 · p. 11
- When only the first N−1 homology groups’ free generators are needed, selecting S from PN+1 can reduce LNAN to columns EN+1−S.The passage states that Pm need not be computed for m>N in this setting.Source: §6 · p. 11
- A priori matching choices can avoid constructing large portions of the top-dimensional boundary operator and underlying complex, reducing memory costs by several orders of magnitude.The reported reduction applies when the matching can be determined before the boundary matrix is constructed.Source: §6 · p. 11
7. EXPERIMENTS
The experiments benchmark EIRENE on persistent homology of random point clouds and published Vietoris–Rips examples, and on higher-dimensional homology of fixed combinatorial complexes. They report a 10,000-point example whose 2-skeleton has over 160 billion simplices, while noting that acyclic compression has limits on difficult unfiltered complexes.
7. EXPERIMENTS
- The first experiments measure elapsed time and heap memory for persistent homology with generators in dimensions 1–3 on random Vietoris–Rips point clouds in R20, with n up to 240.The samples are drawn uniformly from the unit cube; Table 1 describes the persistence and compression-ratio measures.Source: §7 · p. 11, Table 1 · p. 12
- The published-benchmark round reuses C. elegans, Klein, HIV, Dragon 1, and Dragon 2 data from [18] and adds the RG1E4 random geometric complex.Table 2 reports one-dimensional persistence for these Vietoris–Rips complexes.Source: §7 · p. 11, Table 2 · p. 12
- The reported complex has a 2-skeleton with over 160 billion simplices and was, at the time of writing, the largest complex whose homology the authors had computed.All instances in Table 2 record computation of persistent H1.Source: §7 · p. 12
- Acyclic compression has limits on higher-dimensional homology of fixed matching and chessboard complexes, which combine few vertices with many higher-dimensional simplices and relatively large homology.These results concern unfiltered complexes, including the chessboard complex C8,8 and matching complex M3,13.Source: §7 · p. 12, Table 3 · p. 13
- Figure 3 compares |E4|, |X4|, and |M4| with dim ∂4(E4) as sample size k varies, averaging statistics across 10 samples.Black, red, and blue encode |E4|, |X4|, and |M4|, respectively.Source: Figure 3 · p. 13