next up previous

8.3 Sparse Factorization

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.