next up previous
Next: Recursive Spectral Bisection-Based Up: Ordering Sparse Matrices Previous: Ordering Sparse Matrices

Minimum Degree Ordering

Minimum-degree ordering has been used in our research in a two-fold manner:

  1. to order symmetric power system admittance matrices to provide baseline orderings with which to compare the performance of other ordering techniques
  2. to order the independent sub-matrices in recursive spectral bisection and node-tearing ordering techniques
Minimum degree ordering is a greedy algorithm that selects a node with a minimum number of connected edges in the graph for factoring next, or the row to be factored next is that row with a minimum number of variables [5]. This algorithm is not optimal because truly efficient techniques do not exist to resolve ties and numerous rows have equal numbers of elements. Various versions of minimum degree ordering exist, with some versions employing heuristics to minimize the number of calculations. Examples of recursive spectral bisection-based ordering and node-tearing-based ordering are presented below. To contrast the performance of those ordering techniques, figure 3 illustrates a minimum degree ordering of the BCSPWR09.PSA matrix from the Boeing-Harwell series [4]. This matrix represents an actual 1723 bus western US power network, and will be used for all ordering comparisons. Note that the matrix is the most sparse in the upper left-hand corner, while the matrix is less sparse in the lower right-hand corner. When factoring this matrix, the number of zero values that become non-zero while factoring the matrix, is 2,168. Original nonzero values are represented in this figure in black, fillin locations are represented in gray, and all remaining zero values are white. A bounding box has been placed around the sparse matrix.

 
Figure 3: Minimum Degree Ordering  



David P. Koester
Sun Oct 22 17:45:03 EDT 1995