phlite

/flaɪt/

Persistent homology that's light on memory usage.

Background

The current state-of-the-art for computing persistent homology (PH) is Ripser; according to their repository:

Currently, Ripser outperforms other codes [...] by a factor of more than 40 in computation time and a factor of more than 15 in memory efficiency.

The importance of memory efficieny cannot be overstated:

• memory usage is typically the limiting factor for PH (especially on consumer-grade hardware);
• allocating memory is time-consuming, thus limiting applications even on large computers.

The excellent memory efficiency of Ripser has made it, and by extension the Vietoris-Rips (VR) filtration, the go-to suggestion for many applications. Since Ripser is ruthlessly optimised for the VR filtration, it has been regularly forked and adapted to work for other filtations (for example Flagser [3] and Cubical Ripser [4]).

The goal of this library is to separate out the components of Ripser that are specialised to the VR filtration from those that are applicable more boardly. As such, we provide a framework for developing fast, memory-efficient software to compute the persistent homology of novel filtrations.

Related Work

Ripser has been ported to a number of languages, including Ripser.py for Python [5] and Ripserer.jl for Julia [6]. The latter exposes APIs that achieve the same aims as phlite, namely:

Ripserer is designed to be easily extended with new simplex or filtration types.

For those familiar with the Julia language, we strongly recommend this library.

Usage

At its core, phlite is a framework for implementing lazy oracles for sparse matrices $D$ where the rows and columns can be indexed by arbitrary (ordered types). Unlike Ripser, phlite is batteries not included. In order to use the library, you must

• choose appropriate types to index your matrix;
• implement a matrix oracle which can report the non-zero entries in a given column;
• compute an ordered basis for the column space of $D$ (typically in reverse filtration order).

Given such an implementation, phlite provides memory-efficient methods for computing $R = D V$ decompositions and hence computing persistent homology. In line with Ripser's approach, the output of these methods is an oracle for the matrix $V$, from which $R$ can be readily computed. In particular, when the implementation of $D$ satisfies sufficient constraints, phlite provides an implementation of the clearing optimisation (first introduced in [2]).

For more details, please refer to the documentation on docs.rs. If you need support implementing phlite traits for your specific application, please get in touch!

Crates

• phlite - Core library, matrix oracle traits, reduction algorithms.
• phlite_rips - Implementation of VR filtration, à la Ripser. Rust library + basic CLI.
• phlite_grpph - Implementation of GrPPH [7]. Rust library + Python bindings via PyO3.

TODO

High Priority

• Investigate apparent and emergent pairs
• Documentation all traits and APIs
• Tests (unit + integration + property)
• Explain Rips implementation in docs
• Add a trait that captures ability to compute involuted PH representatives
• Implement lockfree reduction algo
• Implement dynamic priority queues (as done in Flagser)

Medium priority

• Improve handling of binary-heap column addition

Low priority

• Optional parallel construction of Rips basis
• Add optional logging
• Write some Rust examples
• Ripser comaptible CLI?
• Web interface for Rips?
• Python bindings?
• Serialisation of V matrices
• Implement magnitude homology
• Implement directed flag complex
• Add suggested citation

References

[1] Bauer, Ulrich. "Ripser: efficient computation of Vietoris–Rips persistence barcodes." Journal of Applied and Computational Topology 5.3 (2021): 391-423. Github repo.

[2] Chen, Chao, and Michael Kerber. "Persistent homology computation with a twist." Proceedings 27th European workshop on computational geometry. Vol. 11. 2011.

[3] Lütgehetmann, Daniel, et al. "Computing persistent homology of directed flag complexes." Algorithms 13.1 (2020): 19. Github repo.

[4] Kaji, Shizuo, Takeki Sudo, and Kazushi Ahara. "Cubical ripser: Software for computing persistent homology of image and volume data." arXiv preprint arXiv:2005.12692 (2020). Github repo.

[5] Tralie, Christopher, Nathaniel Saul, and Rann Bar-On. "Ripser. py: A lean persistent homology library for python." Journal of Open Source Software 3.29 (2018): 925. Github repo.

[6] Čufar, Matija. "Ripserer. jl: flexible and efficient persistent homology computation in Julia." Journal of Open Source Software 5.54 (2020): 2614. Github repo. Docs.

[7] Chaplin, T., Harrington, H.A. and Tillmann, U., 2022. Grounded persistent path homology: a stable, topological descriptor for weighted digraphs. arXiv preprint arXiv:2210.11274.