This research is based upon a factorization algorithm commonly attributed to Crout [5,13]. We modify it to yield the general sequential sparse factorization algorithm presented in figure 3.
Figure 3: Sparse Crout LU Factorization
Element level dependencies for each of the two steps of this algorithm
are illustrated in figure 4 for a general sparse matrix.
To update a non-zero value in the lower triangular portion
of the matrix (L), non-zero column elements
in the upper
triangular portion of the matrix are multiplied with corresponding
non-zero row elements
in the lower triangular portion of the
matrix. The second update step modifies values
in the upper
triangular portion of the matrix (U) by multiplying non-zero lower
triangular row elements
by corresponding upper triangular
column elements
. The LU matrix is over-specified so the
values on the diagonal of either the upper or lower triangular matrix
portions can be set equal to one [5,13]. In Crout's
implementation, the diagonal values of L are stored in the original
diagonal matrix positions, while the diagonal values of U are all
equal to 1 but never explicitly stored.
Figure 4: Element Level Dependencies for General Sparse LU Factorization