next up previous
Next: A Survey of Up: Direct Methods Previous: Choleski Factorization

Ordering Sparse Matrices for Direct Methods

Position symmetric sparse matrices can be represented by graphs with elements in equations corresponding to undirected edges in the graph [12,29]. The motivating applications for this research have position symmetric or position symmetric sub-matrices that are derived from power system networks that in turn, have graph representations. Ordering a symmetric sparse matrix modifies the order in which nodes are factored and 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 by affecting the amount of fillin. Fillin are those matrix locations with zeros as initial values that become non-zeros during factorization.

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 [29]. 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 gif 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 selecting the next node for elimination that has the lowest degree or least number of connected edges. Minimum-degree ordering is closely related to Markowitz ordering [12] --- both heuristics select the next row/column to eliminate that has the least row/column elements. The node-tearing-based ordering technique is utilized to generate block-diagonal-bordered form sparse matrices, and minimum degree ordering is used to minimize fillin locally in the mutually independent blocks and the borders. This technique is commonly referred to as multiple minimum degree ordering [13,22]. Additional detail on minimum degree-based sparse matrix ordering is presented in appendix gif.

 
Figure: 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 gif 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 gif. 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
Next: A Survey of Up: Direct Methods Previous: Choleski Factorization



David P. Koester
Sun Oct 22 17:27:14 EDT 1995