GPU implementation about rivet HOT 7 CLOSED

For ordinary persistence, what Oleg says is consistent with my understanding of things.

Let me try to clarify about parallelization and RIVET. RIVET does a number of different computations, and for each one can ask whether parallelization could be useful. In particular, to support its interactive visualization, RIVET computes a data structure called an augmented arrangement, and this is done in several steps. Here is a rough outline:
1)Starting from data, RIVET first computes a non-minimal presentation of a homology module.
2)RIVET minimizes this presentation.
3)RIVET computes a line arrangement.
4)RIVET computes a barcode for every face in the line arrangement.

Of these steps, 1) is most similar to standard persistence computation, and is also the bottleneck at present for most of the examples we have been looking at. The implementation we have could be improved using ideas similar to those used in state-of-the-art 1-parameter persistence computations, and some ideas for that are mentioned here. But I don't have any ideas for improvements involving parallelization, let alone GPUs.

The algorithm we use for 2) is embarrassingly parallel, and we in fact have a parallel implementation of this. This is explained in the paper linked above. It seems plausible that GPU computation could work well for this, but I really don't know enough about GPU computation to say.

Step 3) is a standard computational geometry computation. I don't know whether parallelization can be useful here, but if it can be, I imagine the computational geometers would have already looked into this.

Step 4) is also embarrassingly parallel. We did some preliminary work in the direction of parallelizing this, but never actually did it. Step 4) used to be the major bottleneck for RIVET, but after we introduced minimal presentations into the RIVET pipeline, the cost of this step became negligible on many examples of interest to us, compared to the cost of 1) and 2). That is because 4) now takes a minimal presentation as input, and the minimal presentation is often surprisingly small in practice. So recently, our focus has been more on 1) and 2). I think it is still worthwhile to parallelize 4), as I believe there are some computations for which this would lead to significant gains, but we regard this as less urgent than we used to. I have no reason to that think that a GPU-based approach would be useful here, but again, I don't enough about GPU computation to say for sure.

from rivet.

I don't know about this myself. As far as I know, it has not been discussed much, if at all, among the RIVET developers. There are a lot of similarities between some of the computations RIVET does (e.g., presentation computation) and ordinary persistence computation. To understand this question, it might make sense to first ask what GPUs can offer to ordinary persistence computation. Although persistent homology computation has been very thoroughly studied, I am not aware of any work which uses GPUs for this.

from rivet.

I believe if there is some linear system of equation to solve there could be a GPU implementation for parallelization. e.g. the decomposition methods are scalable by parallel computing.

from rivet.

As far as I know, persistent homology algorithm is sequential. There were attempts to split the boundary matrix in chunks, but it actually does not add much speedup.

from rivet.

That is strange since RIVET seems to fully utilize the multi-core CPU implementation so I assume the algorithm is working in parallel at least from my superficial observation.

from rivet.

Thanks a lot for the comprehensive explanation.

from rivet.

Recently, I learned that a paper by Greg Henselman and others uses GPU computations to speed up persistent homology computations in the software package Eirene. I do not know the details, but is conceivable that some of the ideas translate to the computation of presentations in the 2-parameter setting.

from rivet.