Fast updates to discrete vector fields speed up persistent homology computations
Updating a Discrete Morse Vector Field for a Lower Star Filtration Vineyard
Computational Geometry
Summary
Persistent homology is a technique used to find shapes and patterns in complex data by analyzing geometric structures. The authors created a special way to organize and update how these shapes are studied when small changes happen in the data. Their method allows quick recalculations without starting from scratch, making it faster to track changes in the patterns as the data changes. They provide code and show their method works as fast as standard ways in a common application.
What this means in practice
- •For topological data analysts: Update persistent homology computations quickly after small changes in vertex orderings to speed up data shape analysis workflows.
- •For computational geometry developers: Incorporate efficient updates to discrete Morse vector fields into software that computes filtrations on complex geometric datasets.
Authors
Kevin Woytowich, Nkechi Nnadi, Elizabeth Munch
Abstract
In this paper, we provide a construction of an acyclic discrete vector field that is compatible with a total order associated with a lower star filtration on a simplicial complex, called the colex vector field. We show that the colex vector field induces a filtered acyclic vector field, whose resulting Morse complex computes the persistent homology of the lower star filtration on the underlying simplicial complex. We show that the colex vector field can be recomputed quickly when the vertex function that induces the lower star filtration is modified via order-adjacent vertex swaps. We provide a framework for storing and computing the number of paths between cells in the simplicial complex, as well as a method to update these values quickly when the colex vector field changes. Finally, we provide publicly available proof-of-concept code for the ideas shown. When applying it to the Persistent Homology Transform, we show that its runtime is comparable to a more standard matrix reduction approach.