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 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
, 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 . A sequential sparse factorization algorithm is
presented in figure
, and we present sequential sparse
forward reduction and backward substitution algorithms for Choleski
factorization in figures
and
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