There are three basic types of algorithms for Cholesky factorization,
depending on which of the three indices is placed in the outer loop:
- (1)
- Row-Cholesky:
Taking i in the outer loop, successive rows of L are computed one
by one, with the inner loops solving a triangular system for each new
row in terms of the previously computed rows.
- (2)
- Column-Cholesky:
Taking j in the outer loop, successive columns of L are computed
one by one, with the inner loops computing a matrix--vector product that
gives the effect of previously computed columns on the column currently
being computed.
- (3)
- Submatrix-Cholesky:
Taking k in the outer loop, successive columns of L are computed
one by one, with the inner loops applying the current column as a
rank-1 update to the remaining unreduced submatrix.
These three families of algorithms have markedly different memory
reference patterns in terms of which parts of the matrix are accessed
and modified at each stage of the factorization, as illustrated in
Figure 5, and each has its advantages and
disadvantages in a given context.
Figure 5: Three forms of Cholesky factorization.