A newer version of this document is available. Customers should click here to go to the newest version.
Visible to Intel only — GUID: GUID-9EAD3754-FD88-4D9E-882C-184E9DA67429
Visible to Intel only — GUID: GUID-9EAD3754-FD88-4D9E-882C-184E9DA67429
Sparse Storage Formats
There are a variety of matrix storage formats available for representing a sparse matrix. The Intel® oneAPI Math Kernel Library (oneMKL) Sparse BLAS library provides support for the following sparse matrix formats:
Sparse Matrix Formats Supported in oneMKL Sparse BLAS |
|---|
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 (num_rows, num_cols), as well as three data arrays: rowptr, colinds and values, and the index_base parameter. Some versions of this format also explicitly store the number of non-zero elements (nnz) but this can be extracted from the rowptr array as described below in the description of the rowptr so we will not include it here.
CSR Matrix Format 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. |
values |
An array that contains the non-zero elements of the sparse matrix stored row by row. |
colinds |
An integer array of column indices for non-zero elements stored in the values array, such that colinds[i] is the column number (using zero- or one-based indexing) of the element of the sparse matrix stored in values[i]. |
rowptr |
An integer array of size equal to num_rows + 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 rowptr[j] - index. The last element of the rowptr array (rowptr[num_rows]) stores the sum of the number of non-zero elements (nnz) and index. That is, nnz = rowptr[num_rows] - index. |
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.
num_rows |
3 |
||||
num_cols |
3 |
||||
index |
0 |
||||
rowptr |
0 |
2 |
4 |
5 |
|
colinds |
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.
num_rows |
4 |
||||||
num_cols |
5 |
||||||
index |
1 |
||||||
rowptr |
1 |
3 |
6 |
6 |
8 |
||
colinds |
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 colinds 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.
num_rows |
4 |
|||||||||
num_cols |
5 |
|||||||||
index |
0 |
|||||||||
rowptr |
0 |
2 |
5 |
8 |
10 |
|||||
colinds |
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 |
1.0 |
3.0 |