Compressed Sparse Row (CSR)
One of the most common sparse formats is the CSR (sometimes called 3-array CSR or CSR3) format that is represented by scalar sizes (nrows, ncols, nnz), as well as three data arrays: row_ptr, col_ind and values, and the index_base parameter.
CSR Matrix Format Elements |
Description |
|---|---|
nrows |
Number of rows in the sparse matrix. |
ncols |
Number of columns in the sparse matrix. |
nnz |
Number of stored elements (sometimes called number of non-zeros) in the sparse matrix. |
index |
Parameter that is used to specify whether the matrix has zero or one-based indexing. |
values |
An array that contains the nnz stored element values of the sparse matrix stored row by row. |
col_ind |
An integer array of nnz column indices for the stored (sometimes called non-zero) elements stored in the values 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 values[i]. |
row_ptr |
An integer array of size equal to nrows + 1. Element j of this integer array gives the position of the element in the values 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[nrows]) stores the sum of nnz and index. That is, nnz = row_ptr[nrows] - index. |
The 3-array CSR format that oneMKL supports has sorted rows by definition. However, the column indices within each row may or may not be sorted (in ascending order) leading to a possibility of unsorted data. The CSR format (with no repeated column indices that oneMKL currently requires) has a unique sorted form. However, in order to provide complete functional support for CSR matrices in either situation, oneMKL assumes CSR matrix handles to be unsorted by default. If the CSR format arrays are known to be in sorted form where all column indices within each row are sorted in ascending order, then users are strongly encouraged to provide that information to oneMKL through the sparse::set_matrix_property() API to possibly allow better algorithm choices and optimizations to deliver better performance. This is particularly important for APIs like triangular solve or sparse matrix addition.
A summary of sorted states for CSR format is given in the table below.
CSR Sortedness State |
Description |
Appropriate oneMKL sparse::property |
|---|---|---|
Unsorted |
Column indices within each row may not be ordered |
None (default) |
Sorted |
Sorted by rows and sorted by columns within each row |
sparse::property::sorted |
Examples of CSR format
The following 3 examples show how the sparse CSR format can be used:
CSR Case 2: Sorted rectangular matrix with one-based indexing and an empty row
CSR Case 3: Unsorted rectangular matrix with zero-based indexing
CSR Case 1: Sorted square matrix with zero-based indexing
Assuming zero-based indexing and a real square matrix.
nrows |
3 |
||||
ncols |
3 |
||||
nnz |
5 |
||||
index |
0 |
||||
row_ptr |
0 |
2 |
4 |
5 |
|
col_ind |
0 |
2 |
1 |
2 |
0 |
values |
1.0 |
2.0 |
-1.0 |
4.0 |
3.0 |
CSR Case 2: Sorted rectangular matrix with one-based indexing and an empty row
Assuming one-based indexing and real rectangular matrix with an empty row.
nrows |
4 |
||||||
ncols |
5 |
||||||
nnz |
7 |
||||||
index |
1 |
||||||
row_ptr |
1 |
3 |
6 |
6 |
8 |
||
col_ind |
1 |
3 |
2 |
3 |
5 |
1 |
4 |
values |
1.0 |
2.0 |
-1.0 |
4.0 |
1.0 |
3.0 |
1.0 |
CSR Case 3: Unsorted rectangular matrix with zero-based indexing
Unsorted CSR example: Assuming zero-based indexing and a real rectangular matrix, we note that the CSR format does not require column indices to be sorted within a given row, but values and col_ind arrays must be consistent with each other. Having the sorted property is not necessary, but can lead to better performance in actual runs due to better algorithms and data locality being enabled. See sparse::set_matrix_property() and sparse::sort_matrix for more details on how one could set the sorted property when it is applicable or reorder the matrix to achieve it when desired.
nrows |
4 |
|||||||||
ncols |
5 |
|||||||||
nnz |
10 |
|||||||||
index |
0 |
|||||||||
row_ptr |
0 |
2 |
5 |
9 |
10 |
|||||
col_ind |
0 |
2 |
4 |
1 |
2 |
1 |
2 |
0 |
3 |
0 |
values |
1.0 |
2.0 |
1.0 |
-1.0 |
4.0 |
2.0 |
3.0 |
1.0 |
4.0 |
3.0 |