Compressed Sparse Row (CSR) Format - 5.2 English - 68552

CSR (Compressed Sparse Row) is a common storage format for sparse matrices that stores all the nonzero elements in the row-wise order, i.e., all nonzeros of the first row are followed by all nonzeros in the second row, etc. The elements within the row can be stored in any order but it is often beneficial to have them sorted in the increasing order of their column indices.

The CSR format of a M x N sparse matrix with NNZ elements uses three arrays as follows:

• row_ptr: Array of size M+1 that contains pointers to the start of each row in the col_idx and val arrays. The last element points to the total number of nonzero elements. The number of nonzeros in row i can be computed as row_ptr[i+1] - row_ptr[i].

• col_idx, val: Arrays of size NNZ containing the column indices and the corresponding values of each nonzero element, respectively.

CSR format can either use 0-based indexing (C, C++) where row and column indices start from 0 or 1-based (Fortran) where indices start from 1.

The above diagram shows a 4 x 5 matrix in CSR storage format with zero-based indexing.

• M = 4, N = 5, NNZ = 6

• row_ptr[M+1] = {0, 1, 1, 4, 6}

• col_idx[NNZ] = {1, 0, 1, 4, 3, 4}

• val[NNZ] = {1.5, 3.0, 3.4, 4.2, 5.4, 6.0}