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.
