25 releases
0.10.1 | Feb 21, 2024 |
---|---|
0.9.2 | May 15, 2023 |
0.8.0 | Mar 24, 2023 |
77 downloads per month
Used in alphalpha
93KB
2K
SLoC
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
Morozov, Dmitriy, and Arnur Nigmetov. "Towards lockfree persistent homology." Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures. 2020.
Bauer, Ulrich, et al. "Phat–persistent homology algorithms toolbox." Journal of symbolic computation 78 (2017): 76-90. Bitbucket
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
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
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.
Dependencies
~3–9MB
~85K SLoC