lophat 0.2.0

No project description provided

LoPHAT

Lockfree Persistent Homology Algorithm Toolbox

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 memory managment 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).
• Rather than split the matrix into chunks, we use a work-stealing paradigm, via the rayon library.

Warning LoPHAT is currently in alpha. The implementation is not optimised, the API is not fixed and tests are limited. Use at your own risk.

Usage in Python

The Python bindings can be installed via

pip install lophat

This provides you with two functions, both of which return the diagram as a set of paired columns and a set of unpaired columns. They both compute these pairings via $R=DV$ decomposition but via different algorithms

• compute_pairings_serial - using standard algorithm, in serial;
• compute_pairings - using the lockfree algorithm of [1].

For example usage, consult the file example.py

TODO

• Implement clearing optimisation when V not required
• Increase property testing
• Write unit tests
• Write Python documentation
• Benchmark
• Add alternative column representations
• Abstract out matrix trait

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