There is definitely a lot of room for improvement as far as the implementation goes. For example, we can deviate a bit from this algorithm by running shortcutting until convergence before going back to hooking as described in Section 6.4 of the Gunrock paper. This could improve the number of iterations it takes to get to convergence.
The performance of the algorithm is described in the revised GraphBLAST paper.
We also add 2 GraphBLAS extension methods called assignScatter and extractGather. What they allow us to do is treat a graphblas::Vector object's values as being the same thing as an graphblas::Index array. This semantic works regardless of whether the graphblas::Vector is using sparse or dense storage. This is particularly valuable from the GPU perspective, because it allows us to avoid having to copy the indices, which may be an intermediate result of a calculation from GPU-to-CPU to form the indices in CPU memory in order to be able to:
1) assign (scatter) to those indices; or
2) extract (gather) from those indices.
This PR adds Connected Components implemented using the FastSV algorithm: Zhang, Azad, Hu. FastSV: A Distributed-Memory Connected Component Algorithm with Fast Convergence (SIAM PP20).
There is definitely a lot of room for improvement as far as the implementation goes. For example, we can deviate a bit from this algorithm by running shortcutting until convergence before going back to hooking as described in Section 6.4 of the Gunrock paper. This could improve the number of iterations it takes to get to convergence.
The performance of the algorithm is described in the revised GraphBLAST paper.
We also add 2 GraphBLAS extension methods called assignScatter and extractGather. What they allow us to do is treat a graphblas::Vector object's values as being the same thing as an graphblas::Index array. This semantic works regardless of whether the graphblas::Vector is using sparse or dense storage. This is particularly valuable from the GPU perspective, because it allows us to avoid having to copy the indices, which may be an intermediate result of a calculation from GPU-to-CPU to form the indices in CPU memory in order to be able to:
1) assign (scatter) to those indices; or
2) extract (gather) from those indices.