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 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.
Intel® oneAPI Math Kernel Library
The sparse matrix storage format for direct sparse solvers is specified by three arrays:
Intel® oneAPI Math Kernel Library
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 thevaluesarray using the row-major upper triangular storage mapping described above.
- columns
- Elementiof the integer arraycolumnsis the number of the column that contains thei-th element in thevaluesarray.
- rowIndex
- Elementjof the integer arrayrowIndexgives the index of the element in thevaluesarray that is first non-zero element in a rowj.
The length of the
values
and
columns
arrays
is equal to the number of non-zero elements in the matrix.
As the
and
.
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
]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 sparse storage scheme for the direct sparse solvers supports both one-based indexing and zero-based indexing.
Intel® oneAPI Math Kernel Library
Consider the symmetric matrix
A
:

Only elements from the upper triangle are stored. The
actual arrays for the matrix
A
are as
follows:
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 thevaluesarray in the order in which they occur in the row (from left to right);
- no diagonal element can be omitted from thevaluesarray 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.