Sparse Storage Formats
Compressed Sparse Row (CSR)
There are a variety of matrix storage formats available for representing
the sparse matrix. One of the most popular is the CSR format that is
represented by three arrays:
row_ptr
, col_ind
and val
, and
the index parameter.CSR Matrix Elements | Description |
|---|---|
num_rows | Number of rows in the sparse matrix. |
num_cols | Number of columns in the sparse matrix. |
index | Parameter that is used to specify whether the matrix has zero or one-based indexing. |
val | An array that contains the non-zero elements of the sparse matrix stored row by row. |
col_ind | An integer array of column indices for non-zero elements stored in the val array, such that col_ind[i] is the
column number (using zero- or one-based indexing) of the element of the sparse matrix stored in val[i] . |
row_ptr | An integer array of size equal to num_rows + 1. Element j of this integer array gives the position of the element
in the val array that is first non-zero element in a row j of A . Note that this position is equal to
row_ptr[j] - index . The last element of the row_ptr array (row_ptr[num_rows] ) stores the sum of, number
of nonzero elements and index *(number of nonzero elements + index *). |
Examples of CSR format
A sparse matrix can be represented in a CSR format in the following ways:
Case 1:
Assuming zero-based indexing and a real square matrix.
num_rows | 3 | ||||
num_cols | 3 | ||||
index | 0 | ||||
row_ptr | 0 | 2 | 4 | 5 | |
col_ind | 0 | 2 | 1 | 2 | 0 |
val | 1.0 | 2.0 | -1.0 | 4.0 | 3.0 |
Case 2:
Assuming one-based indexing and real rectangular matrix with an empty row.
num_rows | 4 | ||||||
num_cols | 5 | ||||||
index | 1 | ||||||
row_ptr | 1 | 3 | 6 | 6 | 8 | ||
col_ind | 1 | 3 | 2 | 3 | 5 | 1 | 4 |
val | 1.0 | 2.0 | -1.0 | 4.0 | 1.0 | 3.0 | 1.0 |