DSS Structurally Symmetric Matrix
Storage
Direct sparse solvers can also solve symmetrically
structured systems of equations. A symmetrically structured system of equations
is one where the pattern of non-zero elements is symmetric. That is, a matrix
has a symmetric structure if
is not zero if and only
if
is not
zero. From the point of view of the solver software, a "non-zero" element of a
matrix is any element stored in the
a
j
,i
a
i
,
j
values
array,
even if its value is equal to 0. In that sense, any non-symmetric matrix can be
turned into a symmetrically structured matrix by carefully adding zeros to the
values
array.
For example, the above matrix
B
can be turned
into a symmetrically structured matrix by adding two non-zero entries:
The matrix
B
can be
considered to be symmetrically structured with 15 non-zero elements and
represented as:
one-based indexing | ||||||||||||||||
values | =
| (1
| -1
| -3
| -2
| 5
| 0
| 4
| 6
| 4
| -4
| 2
| 7
| 8
| 0
| -5)
|
columns | =
| (1
| 2
| 4
| 1
| 2
| 5
| 3
| 4
| 5
| 1
| 3
| 4
| 2
| 3
| 5)
|
rowIndex | =
| (1
| 4
| 7
| 10
| 13
| 16)
| |||||||||
zero-based indexing | ||||||||||||||||
values | =
| (1
| -1
| -3
| -2
| 5
| 0
| 4
| 6
| 4
| -4
| 2
| 7
| 8
| 0
| -5)
|
columns | =
| (0
| 1
| 3
| 0
| 1
| 4
| 2
| 3
| 4
| 0
| 2
| 3
| 1
| 2
| 4)
|
rowIndex | =
| (0
| 3
| 6
| 9
| 12
| 15)
|
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.