Java Reference
In-Depth Information
a 00 0 0 0
a 10 a 11 0 0
a 20 a 21 a 22 0
a 30 a 31 a 32 a 33
(a)
a 00 a 01 a 02 a 03
0
a 11 a 12 a 13
0
0
a 22 a 23
0
0
0
a 33
(b)
Figure12.6 Triangular matrices. (a) A lower triangular matrix. (b) An upper
triangular matrix.
the lower-indexed vertex. In this case, only the lower triangle of the matrix can
have non-zero values.
We can take advantage of this fact to save space. Instead of storing n(n + 1)=2
pieces of information in an nn array, it would save space to use a list of length
n(n + 1)=2. This is only practical if some means can be found to locate within the
list the element that would correspond to position [r, c] in the original matrix.
We will derive an equation to convert position [r, c] to a position in a one-
dimensional list to store the lower triangular matrix. Note that row 0 of the matrix
has one non-zero value, row 1 has two non-zero values, and so on. Thus, row r
is preceded by r rows with a total of P k=1 k = (r 2 + r)=2 non-zero elements.
Adding c to reach the cth position in the rth row yields the following equation to
convert position [r, c] in the original matrix to the correct position in the list.
matrix[r;c] = list[(r 2 + r)=2 + c]:
A similar equation can be used to convert coordinates in an upper triangular matrix,
that is, a matrix with zero values at positions [r, c] such that r > c, as shown in
Figure 12.6(b). For an nn upper triangular matrix, the equation to convert from
matrix coordinates to list positions would be
matrix[r;c] = list[rn (r 2 + r)=2 + c]:
A more difficult situation arises when the vast majority of values stored in an
nm matrix are zero, but there is no restriction on which positions are zero and
which are non-zero. This is known as a sparse matrix.
One approach to representing a sparse matrix is to concatenate (or otherwise
combine) the row and column coordinates into a single value and use this as a key
in a hash table. Thus, if we want to know the value of a particular position in the
matrix, we search the hash table for the appropriate key. If a value for this position
is not found, it is assumed to be zero. This is an ideal approach when all queries to
the matrix are in terms of access by specified position. However, if we wish to find
the first non-zero element in a given row, or the next non-zero element below the
current one in a given column, then the hash table requires us to check sequentially
through all possible positions in some row or column.
 
Search WWH ::




Custom Search