In Algorithm 8.1,
the modification of a given column of the matrix by a
prior column not only changes the existing nonzero entries in the
target column, but may also introduce new nonzero entries in the target
column. Thus, the Cholesky factor **L** may have additional nonzeros,
called * fill*, in locations that were zero in the original matrix
**A**. In determining the storage requirements and computational work,
these new nonzeros that the matrix gains during the factorization are
equally as important as the nonzeros with which the matrix starts out.

The amount of such fill is dramatically affected by the order in which
the columns of the matrix are processed. For example, if the first
column of the matrix **A** is completely dense, then all of the remaining
columns, no matter how sparse they start out, will completely fill in
with nonzeros during the factorization. On the other hand, if a single
such dense column is permuted (symmetrically) to become the last column
in the matrix, then it will cause no fill at all. Thus, a critical
part of the solution process for sparse systems is to determine an
ordering for the rows and columns of the input matrix that limits fill
to preserve sparsity. Unfortunately, finding an ordering that
minimizes fill is a very hard combinatorial problem (NP-complete), but
heuristics are available that do a good job of reducing, if not exactly
minimizing, fill. These techniques include minimum degree, nested
dissection, and various schemes for reducing the bandwidth or profile
of a matrix (see, e.g., [55,56]).
for details
on these and many other concepts used in sparse matrix computations).