One of the key advantages of SPD matrices is that such a sparsity
preserving ordering can be selected in advance of the numeric
factorization, independent of the particular values of the nonzero
entries: only the pattern of the nonzeros matters, not their numerical
values. This would not be the case, in general, if we also had to take
into account pivoting for numerical stability, which obviously would
require knowledge of the nonzero values, and would introduce a
potential conflict between preserving sparsity and preserving
stability. For the SPD case, once the ordering is selected, the
locations of all fill elements in **L** can be anticipated prior to the
numeric factorization, and thus an efficient static data structure can
be set up in advance to accommodate them (this process is usually
called * symbolic factorization*). This feature also stands in
contrast to general sparse linear systems, which usually require
dynamic data structures to accommodate fill entries as they occur,
since their locations depend on numerical information that becomes
known only as the numeric factorization process unfolds. Thus, modern
algorithms and software for solving sparse SPD systems include a
symbolic preprocessing phase in which a sparsity-preserving ordering is
computed and a static data structure is set up for storing the entries
of **L** before any floating point computation takes place.

We introduce some concepts and notation that will be useful in our
subsequent discussion of parallel sparse Cholesky factorization. An
important tool in understanding the combinatorial aspects of sparse
Cholesky factorization is the notion of the * graph* of a symmetric
matrix **A**, which is an undirected graph having **n**
vertices, with an edge between two vertices **i** and **j** if the
corresponding entry of the matrix is nonzero. We denote the
graph of **A** by . The structural effect of the factorization
process can then be described by observing that the elimination of a
variable adds fill edges to the corresponding graph so that the
neighbors of the eliminated vertex become a clique (i.e. a fully
connected subgraph). We also define the * filled graph*, denoted by
, as having an edge between vertices **i** and **j**, with **i > j**,
if in the Cholesky factor **L** (i.e. is
simply with all fill edges added).