next up previous
Next: Ordering Sparse Matrices Up: Direct Methods Previous: LU Factorization

Choleski Factorization

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 inherent numerical stability of this matrix form [12]. A symmetric positive definite sparse matrix A can be numerically factored into a single lower triangular matrix L:

 

Equation gif is solved by setting , and substituting y for . The numerical solution for 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 chapter gif, 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 [29], which is similar to the factorization algorithms commonly attributed to Crout and Doolittle, and similar to the LU algorithm presented in figure gif. A sequential sparse factorization algorithm is presented in figure gif, and we present sequential sparse forward reduction and backward substitution algorithms for Choleski factorization in figures gif and gif respectively. In the backward substitution algorithm, the calculations are performed by implicitly transposing L.

 
Figure: Sparse Column Choleski Factorization 

 
Figure: Sparse Forward Reduction for Choleski Factorization 

 
Figure: Sparse Backward Substitution for Choleski Factorization 



David P. Koester
Sun Oct 22 17:27:14 EDT 1995