U-match factorization: sparse homological algebra, lazy cycle
representatives, and dualities in persistent (co)homology

Persistent homology is a leading tool in topological data analysis (TDA).
Many problems in TDA can be solved via homological -- and indeed, linear --
algebra. However, matrices in this domain are typically large, with rows and
columns numbered in billions. Low-rank approximation of such arrays typically
destroys essential information; thus, new mathematical and computational
paradigms are needed for very large, sparse matrices.
We present the U-match matrix factorization scheme to address this challenge.
U-match has two desirable features. First, it admits a compressed storage
format that reduces the number of nonzero entries held in computer memory by
one or more orders of magnitude over other common factorizations. Second, it
permits direct solution of diverse problems in linear and homological algebra,
without decompressing matrices stored in memory. These problems include look-up
and retrieval of rows and columns; evaluation of birth/death times, and
extraction of generators in persistent (co)homology; and, calculation of bases
for boundary and cycle subspaces of filtered chain complexes. Such bases are
key to unlocking a range of other topological techniques for use in TDA, and
U-match factorization is designed to make such calculations broadly accessible
to practitioners.
As an application, we show that individual cycle representatives in
persistent homology can be retrieved at time and memory costs orders of
magnitude below current state of the art, via global duality. Moreover, the
algebraic machinery needed to achieve this computation already exists in many
modern solvers.