Lockfree Persistent Homology Algorithm Toolbox
Project description
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
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 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
or this Google colab notebook
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
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for lophat-0.3.0-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e21844b4589d3253f2290e681725bad4fa603f2abf1a0af78706638f081bff35 |
|
MD5 | d7540283d7f74e1b73c445e85bdacd37 |
|
BLAKE2b-256 | 10482e85050b0003f9eeacc39c6725e5cb80ea8abbceea5ae56a534eebf0c33d |
Hashes for lophat-0.3.0-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ffebb53a459afbf991c1b08c0357598d5ec5a9698d07ccfef94cd451c3717400 |
|
MD5 | 13f6d6f7cb7e380f1c5e51d44fea7bc9 |
|
BLAKE2b-256 | c495645f896075ab0da9d53d98d6a6389ebad70fedfc4c0f1a3edd4ac45ac185 |
Hashes for lophat-0.3.0-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1c785bf17903c7fe701ef4dffafcbe983cae17847f143f7951906230f55d2da7 |
|
MD5 | 823ee966e432a3dac9038a83675a93a8 |
|
BLAKE2b-256 | 88cc1212699b5003814504c64f5802338d1925e701bec4655837a526e9eff34f |
Hashes for lophat-0.3.0-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 614f6f6517029466a44bac79fc80f60514fb6b2402d2252b5517295db885bf65 |
|
MD5 | ce209711383919d8b5af6247e2bf1d53 |
|
BLAKE2b-256 | e72c94d77076ab689c3d9ce290d9e82ca6bdaf45a52cfcbee86214af99e25386 |
Hashes for lophat-0.3.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 64e1666e50124270491fa6f0f135b7a78a6e788ec4d337e6f814303f1ed36807 |
|
MD5 | b97ad6540a111c6ed2e2d4e577681b50 |
|
BLAKE2b-256 | fe4a96d1bd543fe8048ef9e62393ec0e11c8c344962266ffd479a8485871d97e |
Hashes for lophat-0.3.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d31d9974ff4c23cb5cca1a63a0944f825f47612eec46f1b8a339c65a345c3924 |
|
MD5 | 37cdd0a05e2154d69261981a315d8339 |
|
BLAKE2b-256 | a4d13204b58620fd7c437e3759bdb76d40baa7088bf74ed43b7772df7d7f26e2 |
Hashes for lophat-0.3.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 490556c60d5ae59dad22a11d6e2a2600670820e78d48dcf4d453123533607e67 |
|
MD5 | a665effb6dad0c65631c7e6fc4d26511 |
|
BLAKE2b-256 | 941d2598fbf122993376a8aaa100bfe320c87f2cff8d6cbac521119e9b6c90ca |
Hashes for lophat-0.3.0-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | da5dcd48ff3cd150bd4f5005e3d210b2efb03cce9132f403524201d0573f4972 |
|
MD5 | af7e73b94d0c9bc58215d1b7065f21eb |
|
BLAKE2b-256 | 1b74d46f485c6bf5f7d8f6b74935f0e02c0b0646ce7b7c3683b0694401db4df9 |