Symmetric sparse matrices can be represented by graphs with elements in equations corresponding to undirected edges in the graph [4,14]. Ordering a symmetric sparse matrix is actually little more than changing the labels associated with nodes in an undirected graph, however, this simple task can drastically effect the amount of calculations involved when factoring a sparse matrix. For symmetric positive definite matrices, there is much latitude in the order to perform the calculations, because there is no requirement for pivoting for numerical stability and the only effect of modifying the order of calculations might result from changes in round-off errors [14]. There is a graph-theoretical interpretation for fillin; factoring a node is equivalent to removing the node from the graph, however, any path through the factored node to adjacent edges must remain and must now be explicitly listed. This phenomenon is illustrated in figure 5 for a segment of a graph. In this example, the node with the least number of edges is selected for factoring, and two of three possible new edges are created. Only two new edges are created because there is an existing edge already connecting a pair of nodes. Fillin causes the number of edges in the remaining nodes to increase, often drastically increasing the number of calculations. The amount of fillin generated when any node is factored is bounded by the binomial coefficient of the number of edges at a node choose 2 or
where:¯There are several notable techniques to minimize fillin, with one of the commonly used techniques being minimum-degree ordering. Minimum degree ordering is used in conjunction with the node-tearing-based ordering technique to generate block-diagonal-bordered form sparse matrices. Additional detail on minimum degree-based sparse matrix ordering is presented in appendix A.
is the number of fillin when factoring node k.
is the number of edges at node k.
Figure 5: Graph Theoretical Explanation of Fillin
Modifying the ordering of a sparse matrix is simple to perform using a permutation matrix P of all zeros and ones that simply generates elementary row and column exchanges. Applying the permutation matrix P to the original linear system in equation 1 yields the linear system
that is solved by factoring into the Choleski factor
in
and then performing forward
reduction, backward substitution, and undoing the permutation on the
x vector. These steps would require the solutions of:
As long as the symmetric matrix A is ordered with the permutation
matrix P to , the resultant matrix after ordering remains
symmetric positive definite.