We are considering the direct solution of the linear system
where A is an sparse matrix. The sparse
matrix A can be numerically factored into two separate triangular
matrices, one sparse matrix being lower triangular, L, and the other
sparse matrix being upper triangular, U:
A lower triangular matrix, L, has all zeros above the diagonal and an upper triangular matrix, U, has all zeros below the diagonal [4].
If the matrix A is an symmetric positive definite
sparse matrix, then a special form of LU factorization can be used
that exploits the symmetry and inherently numerical stable
characteristics of this matrix form [4]. Our analysis of the
available parallelism in block-diagonal-bordered Choleski
factorization, presented in section 4, is an extension of the
analysis of available parallelism in block-diagonal-bordered LU
factorization. Additional discussions on the state of the
literature for Choleski factorization are presented below.
For a brief review, the symmetric positive definite sparse matrix A can be numerically factored into a single lower triangular matrix L:
A lower triangular matrix, L, has all zeros above the diagonal.
Equation 3 is solved by setting , and
substituting y for
. The numerical solution for Ly=b is
found by forward reduction, and the numerical solution for x is
calculated by backward substitution in the equation
.
Triangular linear systems can be readily solved numerically by solving
for the first value in the triangular linear system and substituting
that value into subsequent equations.
Sparse Choleski factorization can mirror any dense Choleski factorization algorithm, although generally a sparse matrix algorithm has only one explicit for loop, which can be for any single index in the dense case. The remaining indices are examined only for non-zero values in the original matrix or for non-zero values that will occur from fillin in the matrix. Sparse matrix fillin occurs when a value that formally was zero becomes non-zero in the process of factoring the matrix. Fillin can be controlled in sparse Choleski factorization by ordering the matrix before performing the factorization [4].
As we continue the review of Choleski factorization, we present a general sequential sparse factorization algorithm based upon the column Choleski factorization algorithm [14], which is similar to the factorization algorithms commonly attributed to Crout and Doolittle. This sequential sparse factorization algorithm is presented in figure 2. In addition, we present general sequential sparse forward reduction and backward substitution algorithms in figures 3 and 4 respectively. In the backward substitution algorithm, the calculations are performed by implicitly transposing L.
Figure 2: Sparse Choleski Factorization
Figure 3: Sparse Forward Reduction
Figure 4: Sparse Backward Substitution