next up previous

8.3 Sparse Factorization     continued...

For sparse Cholesky factorization, row-Cholesky is seldom used for a number of reasons, including the difficulty in providing a row-oriented data structure that can be accessed efficiently during the factorization, and the difficulty in vectorizing or parallelizing the triangular solutions required. We will therefore focus our attention on the column-oriented methods, column-Cholesky and submatrix-Cholesky. Expressed in terms of the column operations and and the notation defined earlier, sparse column-Cholesky can be stated as follows:

In column-Cholesky, a given column j of A remains unchanged until the outer loop index reaches that value of j. At that point column j is updated by a nonzero multiple of each column k < j of L for which . After all column modifications have been applied to column j, the diagonal entry is computed and used to scale the completely updated column to obtain the remaining nonzero entries of . Column-Cholesky is sometimes said to be a `left-looking' algorithm, since at each stage it accesses needed columns to the left of the current column in the matrix. It can also be viewed as a `demand-driven' algorithm, since the inner products that affect a given column are not accumulated until actually needed to modify and complete that column. For this reason, Ortega [38] terms column-Cholesky a `delayed-update' algorithm. It is also sometimes referred to as a `fan-in' algorithm, since the basic operation is to combine the effects of multiple previous columns on a single target column. The column-Cholesky algorithm is the most commonly used method in commercially available sparse matrix packages.