Convert COO to CSR format in c++

Question

I have a matrix in the COO format. More specifically, there are three matrices row_index, column_index, value. Can you help me to convert this matrix format in CSR format with an efficient, not computationally expensive way, using C language? Are there libraries for this purpose?

Example:

COO format:

       row_index col_index value
          1         1         1
          1         2        -1
          1         3        -3   
          2         1        -2
          2         2         5
          3         3         4
          3         4         6
          3         5         4
          4         1        -4
          4         3         2
          4         4         7     
          5         2         8
          5         5        -5 

Answer 1

Intel MKL documentation (for mkl_csrcoo) states:

Converts a sparse matrix in the CSR format to the coordinate format and vice versa.

And according to the above link you should set job:

if job(1)=1, the matrix in the coordinate format is converted to the CSR format.

Answer 2

I know this is an old thread, but, assuming the COO data is (i,j) ordered/sorted, as you show, a sequential algorithm to convert from COO to CSR is:

int main()
{
    // Example from Wikipedia (https://en.wikipedia.org/wiki/Sparse_matrix)

    // Matrix:
    // 10 20  0  0  0  0
    //  0 30  0 40  0  0
    //  0  0 50 60 70  0
    //  0  0  0  0  0 80

    // Expected output:
    // csr_val: 10 20 30 40 50 60 70 80
    // csr_col:  0  1  1  3  2  3  4  5
    // csr_row:  0  2  4  7  8

    const int  nnz = 8; // number of non-zero elements
    const int rows = 4; // number of matrix rows
    const int cols = 6; // number of matrix columns

    // coo data:
    double coo_val[nnz] = { 10.0, 20.0, 30.0, 40.0, 50.0, 60.0, 70.0, 80.0 };
    int    coo_row[nnz] = { 0, 0, 1, 1, 2, 2, 2, 3 };
    int    coo_col[nnz] = { 0, 1, 1, 3, 2, 3, 4, 5 };

    // coo to csr:
    double csr_val[nnz]      = { 0 };
    int    csr_col[nnz]      = { 0 };
    int    csr_row[rows + 1] = { 0 };
    for (int i = 0; i < nnz; i++)
    {
        csr_val[i] = coo_val[i];
        csr_col[i] = coo_col[i];
        csr_row[coo_row[i] + 1]++;
    }
    for (int i = 0; i < rows; i++)
    {
        csr_row[i + 1] += csr_row[i];
    }
}

Notice that, assuming the COO data is (i,j) ordered/sorted, csr_col = coo_col and csr_val = coo_val, so you just need to obtain csr_row, and that is as simples as:

int csr_row[rows + 1] = { 0 };
for (int i = 0; i < nnz; i++)
    csr_row[coo_row[i] + 1]++;
for (int i = 0; i < rows; i++)
    csr_row[i + 1] += csr_row[i];

So, in conclusion, you can easily achieve what you want with the 5 lines of code presented above.

Final note:

The proposed method has no considerations for duplicated COO entries.

Answer 3

An implementation of this conversion is included in scipy (open source: BSD-licensed), the function coo_tocsr in particular. It is in C++, but this is only in order to template the data and index types, and in order to initialise a data structure, so it can easily be transformed into C code.