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 (nrows
, ncols
), as well as three data arrays: row_ptr
, col_ind
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 row_ptr
array as described below in the
description of the row_ptr
so we will not include it here.
CSR Matrix Format Elements |
Description |
---|---|
|
Number of rows in the sparse matrix. |
|
Number of columns in the sparse matrix. |
|
Parameter that is used to specify whether the matrix has zero or one-based indexing. |
|
An array that contains the non-zero elements of the sparse matrix stored row by row. |
|
An integer array of column indices for non-zero elements stored in the |
|
An integer array of size equal to |
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 |
||||
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 |
||||||
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 |
|||||||||
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 |
Coordinate (COO) format#
The simplest sparse matrix format is the COO format, represented by scalar sizes
(nrows
, ncols
, nnz
), as well as three data arrays: row_ind
,
col_ind
, and values
, along with an index
parameter. Each tuple,
(row_ind[i], col_ind[i], values[i])
, represents a non-zero value in the
sparse matrix.
COO Matrix Format Elements |
Description |
---|---|
|
Number of rows in the sparse matrix. |
|
Number of columns in the sparse matrix. |
|
Number of non-zero in the sparse matrix. |
|
Parameter that is used to specify whether the matrix has zero or one-based indexing. |
|
An integer array of row indices of non-zero elements in the |
|
An integer array of column indices of non-zero elements in the |
|
An array that contains the non-zero elements of the sparse matrix, preferably but not necessarily stored in a sorted order. |
Examples of COO format#
The following examples show how the sparse COO format can be used:
COO Case 1: sorted rectangular matrix with one-based indexing
COO Case 2: unsorted rectangular matrix with zero-based indexing
COO Case 1: sorted rectangular matrix with one-based indexing#
An example of a rectangular COO matrix in one-based indexing sorted by rows, and then by columns within rows, is given below.
nrows |
4 |
||||||
ncols |
5 |
||||||
nnz |
7 |
||||||
index |
1 |
||||||
row_ind |
1 |
1 |
2 |
2 |
2 |
4 |
4 |
col_ind |
1 |
3 |
2 |
3 |
5 |
1 |
4 |
values |
1.0 |
2.0 |
-1.0 |
4.0 |
1.0 |
3.0 |
1.0 |
COO Case 2: unsorted rectangular matrix with zero-based indexing#
The COO format does not require sorted arrays so long as (row_ind[i], col_ind[i], val[i])
are grouped together in their unsorted order for all i
, representing each non-zero element in
the sparse matrix. 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.
An example of an unsorted COO matrix in zero-based indexing and a real rectangular matrix are given below.
nrows |
4 |
|||||||||
ncols |
5 |
|||||||||
index |
0 |
|||||||||
row_ind |
2 |
1 |
0 |
1 |
2 |
3 |
0 |
1 |
2 |
2 |
col_ind |
1 |
4 |
2 |
1 |
0 |
0 |
0 |
2 |
3 |
2 |
values |
2.0 |
1.0 |
2.0 |
-1.0 |
1.0 |
3.0 |
1.0 |
4.0 |
4.0 |
3.0 |