Numeric factorization algorithms work with nonzero values of a sparse matrix A and the data structures resulting from symbolic factorization to compute the factorization
Algorithms discussed in the current section act on a sparse n × n matrix A. They assume that
A already reflects the pivot strategy defined by P and PT, i.e. the algorithms pivot down the diagonal.
A has zero-valued entries at fill-up locations.
A is maintained in a sparse data structure supporting the get, scan, and put operators. Communication with the data structure is maintained through the buffer a in the normal manner.
Techniques for creating the requisite pivot ordered, fill-up augmented A matrix (i.e. PAPT) are discussed in Section 8.5.
Algorithm 25 uses Doolittle’s method to compute the LU decomposition of a sparse matrix A.The algorithm overwrites A with LU.
for |
while[scan(,row )] finished |
push_scan |
min() |
while[scan(,row )] finished |
if get()is successful |
if |
get() |
put() |
pop_scan |
† Operations and data types are defined in Section 8.2. |
Algorithm 26 uses Doolittle’s method to compute U, the upper triangular factors, of a symmetric sparse matrix A. It is assumed that A is initially stored as an upper triangular matrix. The algorithm overwrites A with U. The vector w is used to construct the nonzero entries of each column from U. The vector c contains cursors to the row in L with which the entries of A are associated, e.g. if wk contains lji then ck is j.
for |
for |
if get()is successful |
get() |
while[scan(,row )] finished |
for |
if get()is successful |
put() |
† Operations and data types are defined in Section 8.2. |
Doolittle’s method for full, asymmetric matrices, is examined in Section 4.2. Doolittle’s method for full, symmetric matrices is discussed in Section 7.4.