LoPHAT

Lockfree Persistent Homology Algorithm Toolbox

Try in: Your Browser • Google Colab

Overview

LoPHAT is a Rust library implementing the lockfree algorithm for computing persistent homology (PH), introduced in [1]. Python bindings are provided via PyO3, with an interface familiar to those who have used PHAT [2].

The primary goal of this library is to make the algorithm accessible to those wishing to compute PH of arbitrary filtered chain complexes. In particular, LoPHAT is not specialised to compute PH of common filtrations or even filtered simplicial complexes. As such, you should expect LoPHAT to under-perform as compared to giotto-ph [3] or oineus [4], both of which use the algorithm of [1].

The only changes from the algorithm described in [1] are:

• We use the pinboard library for epoch-based memory management of the matrices.
• We store the $j^{th}$ column of $R$ and $V$ alongside each other in memory, allowing a full $R=DV$ decomposition (rather than just computing pairings).
• We additionally employ the clearing optimisation [5] and provide methods for anti-transpotion (so as to compute persistent cohomology).
• We distribute chunks via work-stealing, using the rayon library.

Warning LoPHAT is currently in beta. The implementation is not optimised, the API is not fixed and tests are limited.

Usage in Rust

Install with

cargo add lophat

For usage, please consult the Rust docs.

Usage in Python

The Python bindings can be installed via

pip install lophat

If this fails, it is probably pip trying to install from source without a cargo toolchain present. To force installing from binary run

pip install --only-binary lophat lophat

This provides you with one function, compute_pairings, which returns the diagram as a set of paired columns and a set of unpaired columns. By default, this uses all available threads and the lockfree algorithm of [1]. To use serial algorithm or limit number of threads, additionally provide a LoPhatOptions object.

For more details, please consult the Python docs. For example usage, see the file example.py or this Google colab notebook.

TODO

• Change options struct for each algorithm
• Decide on new Python bindings
• Increase property testing
• Write unit tests
• Write integration tests (testing V)
• Benchmark
• Abstract out matrix trait?
• Reduce memory usage when V not maintained
• Add contributing guide
• Fix locking in pivots vector
• Github actions

References

[1] Morozov, Dmitriy, and Arnur Nigmetov. "Towards lockfree persistent homology." Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures. 2020.

[2] Bauer, Ulrich, et al. "Phat–persistent homology algorithms toolbox." Journal of symbolic computation 78 (2017): 76-90. Bitbucket

[3] Pérez, Julián Burella, et al. "giotto-ph: A python library for high-performance computation of persistent homology of Vietoris-Rips filtrations." arXiv preprint arXiv:2107.05412 (2021). GitHub

[4] Nigmetov, Arnur, Morozov, Dmitriy, and USDOE. Oineus v1.0. Computer software. https://www.osti.gov//servlets/purl/1774764. USDOE. 1 Apr. 2021. Web. doi:10.11578/dc.20210407.1. GitHub

[5] Bauer, Ulrich, Michael Kerber, and Jan Reininghaus. "Clear and compress: Computing persistent homology in chunks." Topological Methods in Data Analysis and Visualization III: Theory, Algorithms, and Applications. Springer International Publishing, 2014.