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 [9]. A symmetric positive
definite sparse matrix A can be numerically factored into a single
lower triangular matrix L:
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
. Our
analysis of the available parallelism in block-diagonal-bordered LU
factorization, presented in section 4, can be extended to an
analysis of available parallelism in block-diagonal-bordered Choleski
factorization by simply substituting
for U. Additional
discussions on the state of the literature for Choleski factorization
are presented below.
We present a general sequential sparse factorization algorithm based upon the column Choleski factorization algorithm [20], which is similar to the factorization algorithms commonly attributed to Crout and Doolittle, and similar to the LU algorithm presented in figure 3. A sequential sparse factorization algorithm is presented in figure 6, and we present sequential sparse forward reduction and backward substitution algorithms for Choleski factorization in figures 7 and 8 respectively. In the backward substitution algorithm, the calculations are performed by implicitly transposing L.
Figure 6: Sparse Choleski Factorization
Figure 7: Sparse Forward Reduction for Choleski Factorization
Figure 8: Sparse Backward Substitution for Choleski Factorization