Position symmetric sparse matrices can be represented by graphs with elements in equations corresponding to undirected edges in the graph [9,20]. The motivating applications for this research have position symmetric or have position symmetric submatrices that are derived from power system networks that have graph representations. 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 [20]. Diagonally dominant matrices also can be factored with little concern for pivoting, and there are many applications where time constraints are critical, so in order to speedup sparse LU factorization, pivoting is ignored. If there is no pivoting, ordering can be performed a priori and static data structures can be used for the most efficient sequential algorithm.
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 9 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. This ordering technique is used for position symmetric matrices and attempts to minimize fillin by choosing that node for the next elimination which has the lowest degree or least number of connected edges. Minimum-degree ordering is closely related to Markowitz ordering [9]. Like minimum-degree ordering, Markowitz ordering attempts to select the next row/column to eliminate that has the least row/column elements. 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 9: 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 LU factors
and
in
or the Choleski factor
in
and then performing forward reduction, backward
substitution, and undoing the permutation on the x vector. For LU
factorization, these steps would require the solutions of:
For Choleski factorization, simply substitute for
in equation 6. Also for Choleski
factorization, as long as a symmetric positive definite matrix A is
ordered with the permutation matrix P to
, the resultant
matrix after ordering remains symmetric positive definite.