Using cuSPARSE in nvGraph as the connection matrix?

Question

Title pretty much says it all and I can't find any documentation about this online. I'm interested in implementing a few graph oriented algorithms and my connection matrices are getting rather huge. Is there a way to use cuSPARSE to remove the large amounts of redundancy in my connection matrix? (Since each vertex is connected to really at most 5 others).

I've already implemented graph partitioning to segment and reduce the size of my connection matrix but that leaves me with roughly a 256 x 256 matrix, about half of which is zeros. (Eg: No connection)

for graph topology, `nvGRAPH` already implements sparse definitions. — Robert Crovella, Jun 30 '16 at 01:30
Oh I didnt see that. The documentation on nvgraph seems rather sparse Edit: Accidental pun — Louis Castricato, Jun 30 '16 at 01:39
The documentation is not only "sparse". The wording is horrible as well. CSR and CSC are something that you may have to write down with pen+pencil to wrap your head around. But what essentially are the "column pointers" of the CSC are described as *"Array of size nvertices+1, where i element equals to the number of the first edge for this vertex in the list of all incoming edges in the source_indices array."*. I read it a dozen times, and tried to make sense of it, but failed. In the end, I just verified: These **are** indeed just the column pointers. It's obviously hard to make things easy. — Marco13, Sep 18 '16 at 15:01
CSC and CSR are more completely described in [the cusparse documentation](http://docs.nvidia.com/cuda/cusparse/index.html#matrix-formats). — Robert Crovella, Dec 27 '16 at 16:26

Robert Crovella · Accepted Answer · 2016-12-27T16:27:58.680

nvGRAPH is a new CUDA library available in the CUDA 8RC toolkit. Since CUDA 8RC is a release candidate, not a production release version, the documentation for it only exists in PDF form, not officially online, and these PDF documents are installed when you install the CUDA 8 RC toolkit.

The particular document relative to this new library is nvGRAPH_Library.pdf, the location of which will vary depending on whether you install the CUDA 8RC toolkit on windows or linux, and options you select during the install process.

Is there a way to use cuSPARSE to remove the large amounts of redundancy in my connection matrix?

In fact, the only way to specify the graph topology (which I think is equivalent to your "connection matrix") is via a compressed sparse method. The actual method you use (CSC or CSR) is specified during nvGRAPH configuration/initialization, using the nvgraphTopologyType_t enum:

2.2. nvGRAPH graph topology types

Graphs toplogy types. Defines storage format. Some algorithms can work only with
specific topology types, see algorithms descriptions for the list of supported topologies.

typedef enum
{
NVGRAPH_CSR_32 = 0,
NVGRAPH_CSC_32 = 1,
} nvgraphTopologyType_t;

Topology types

NVGRAPH_CSR_32 Compressed Sparse Rows format (row major format). Used
in SrSPMV algorithm. Use nvgraphCSRTopologyX_t topology
structure for this format.

NVGRAPH_CSC_32 Compressed Sparse Column format (column major format).
Used in SSSP, WidestPath and Pagerank algorithms. Use
nvgraphCSCTopologyX_t topology structure for this format.

This particular enum type would normally be passed to nvGRAPH during initial graph configuration:

// Set graph connectivity and properties (transfers)
nvgraphSetGraphStructure(handle, graph, (void*)CSC_input,NVGRAPH_CSC_32);

More complete code samples/examples are given in the nvGRAPH documentation PDF document in chapter 3 starting on 20, and there are new nvGRAPH sample codes provided in the CUDA 8RC sample codes installation such as nvgraph_Pagerank, nvgraph_SemiRingSpMV, and nvgraph_SSSP (Single Source Shortest Path).

Normal NVIDIA practice is to make these documents available publicly (e.g. here) at the point when the toolkit goes to a production release status.

EDIT: with the release of CUDA 8, these documents referenced above are now publicly available.

Using cuSPARSE in nvGraph as the connection matrix?

1 Answers1