next up previous contents
Next: A Survey of Up: Direct Linear Solvers Previous: Choleski Factorization

Ordering Sparse Matrices

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:¯

is the number of fillin when factoring node k.

is the number of edges at node k.

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.

 
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.



next up previous contents
Next: A Survey of Up: Direct Linear Solvers Previous: Choleski Factorization



David P. Koester
Sun Oct 22 15:31:10 EDT 1995