Developer Reference

  • 2020.2
  • 07/15/2020
  • Public Content
Contents

DSS Symmetric Matrix Storage

For symmetric matrices, it is necessary to store only the upper triangular half of the matrix (upper triangular format) or the lower triangular half of the matrix (lower triangular format).
The
Intel® MKL
direct sparse solvers use a row-major upper triangular storage format: the matrix is compressed row-by-row and for symmetric matrices only non-zero elements in the upper triangular half of the matrix are stored.
The
Intel® MKL
sparse matrix storage format for direct sparse solvers is specified by three arrays:
values
,
columns
, and
rowIndex
. The following table describes the arrays in terms of the values, row, and column positions of the non-zero elements in a sparse matrix.
values
A real or complex array that contains the non-zero elements of a sparse matrix. The non-zero elements are mapped into the
values
array using the row-major upper triangular storage mapping described above.
columns
Element
i
of the integer array
columns
is the number of the column that contains the
i
-th element in the
values
array.
rowIndex
Element
j
of the integer array
rowIndex
gives the index of the element in the
values
array that is first non-zero element in a row
j
.
The length of the
values
and
columns
arrays is equal to the number of non-zero elements in the matrix.
As the
rowIndex
array gives the location of the first non-zero element within a row, and the non-zero elements are stored consecutively, the number of non-zero elements in the
i
-th row is equal to the difference of
rowIndex
(
i
)
and
rowIndex
(
i
+1)
.
To have this relationship hold for the last row of the matrix, an additional entry (dummy entry) is added to the end of
rowIndex
. Its value is equal to the number of non-zero elements plus one. This makes the total length of the
rowIndex
array one larger than the number of rows in the matrix.
The
Intel® MKL
sparse storage scheme for the direct sparse solvers supports both one-based indexing and zero-based indexing.
Consider the symmetric matrix
A
:
Only elements from the upper triangle are stored. The actual arrays for the matrix
A
are as follows:
Storage Arrays for a Symmetric Matrix
one-based indexing
values
=
(1
-1
-3
5
4
6
4
7
-5)
columns
=
(1
2
4
2
3
4
5
4
5)
rowIndex
=
(1
4
5
8
9
10)
 
 
 
zero-based indexing
values
=
(1
-1
-3
5
4
6
4
7
-5)
columns
=
(0
1
3
1
2
3
4
3
4)
rowIndex
=
(0
3
4
7
8
9)
 
 
 

Storage Format Restrictions

The storage format for the sparse solver must conform to two important restrictions:
  • the non-zero values in a given row must be placed into the
    values
    array in the order in which they occur in the row (from left to right);
  • no diagonal element can be omitted from the
    values
    array for any symmetric or structurally symmetric matrix.
The second restriction implies that if symmetric or structurally symmetric matrices have zero diagonal elements, then they must be explicitly represented in the
values
array.