next up previous

8.3 Sparse Factorization     continued...

Similarly, sparse submatrix-Cholesky can be expressed as follows.

In submatrix-Cholesky, as soon as column k has been computed, its effects on all subsequent columns are computed immediately. Thus, submatrix-Cholesky is sometimes said to be a `right-looking' algorithm, since at each stage columns to the right of the current column are modified. It can also be viewed as a `data-driven' algorithm, since each new column is used as soon as it is completed to make all modifications to all the subsequent columns it affects. For this reason, Ortega [38] terms submatrix-Cholesky an `immediate-update' algorithm. It is also sometimes referred to as a `fan-out' algorithm, since the basic operation is for a single column to affect multiple subsequent columns. We will see that these characterizations of the column-Cholesky and submatrix-Cholesky algorithms have important implications for parallel implementations.