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

Author: 

Hang, H
Giusti, C
Ziegelmeier, L
Henselman-Petrusek, G

Publication Date: 

19 August 2021

Last Updated: 

2021-10-22T05:15:22.167+01:00

abstract: 

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.

Symplectic id: 

1191722

Download URL: 

Submitted to ORA: 

Not Submitted

Publication Type: 

Journal Article