Cholesky factorization factors an , symmetric, positive-definite
matrix
into
the product of a lower triangular matrix
and its transpose, i.e.,
(or
, where
is upper triangular).
It is assumed that the lower triangular portion of
is stored
in the lower triangle of a two-dimensional array
and that the computed elements of
overwrite the given elements of
.
At the
-th step, we partition the
matrices
,
,
and
, and write the system as
where the block is
,
is
,
and
is
.
and
are lower triangular.
The block-partitioned form of
Cholesky factorization may be inferred inductively as follows.
If we assume that , the lower triangular Cholesky factor
of
, is known, we can rearrange the block equations,
A snapshot of the block Cholesky factorization algorithm in
Figure 5 shows
how the column panel (
and
) is computed
and how the trailing submatrix
is updated.
The factorization can be done by recursively applying the steps
outlined above to the
matrix
.
Figure 5:
A snapshot of block Cholesky factorization.
In the right-looking version of the LAPACK routine, the computation of the above steps involves the following operations:
The parallel implementation of the corresponding ScaLAPACK routine, PDPOTRF, proceeds as follows: