next up previous
Next: Pseudo-Factorization Up: The Preprocessing Phase Previous: The Preprocessing Phase

Ordering

The preprocessing phase ordering step must identify diagonal matrix blocks while also attempting to minimize the amount of fillin during factorization. Few matrices can be readily ordered into block-diagonal-bordered form with equal workload in each block. The exception to this rule are highly regular matrices from the structural analysis community, where the nested dissection ordering algorithm can produce balanced block-diagonal-bordered matrices [29]. Recursive spectral bisection can be used to partition irregular matrices [3,45,50], and subsequently, the coupling equations can be extracted. Unfortunately, this technique, as well as nested dissection, relies on dividing the matrix into equal sized partitions, without considering the number of coupling equations or considering the number of calculations in each diagonal block. Load-imbalance limits the potential for using recursive spectral bisection, because the number of calculations in a block for factorization or forward reduction/backward substitution are related to the sparsity of the subgraph, which can vary significantly for irregular power systems network matrices [37].

A third method to order a sparse matrix into block-diagonal-bordered form is referred to as node-tearing [12,49], which is a specialized form of diakoptics [26]. This technique attempts to extract the natural structure in the matrix or graph, and generally produces many irregularly sized blocks, while minimizing the number of coupling equations or the size of the lower border and last diagonal block. Additional detail on the node-tearing form of diakoptics is presented in appendix gif. Load balancing techniques must be used after the node-tearing matrix ordering step to distribute the processing load uniformly onto a multi-processor. As shown in chapter gif, diagonal blocks can be assigned to any processor without requirements for interprocessor communications to factor the diagonal block and associated portion of the lower border.

There are several notable techniques to minimize fillin when factoring a sparse matrix, 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 with a minimum number of fillin and resulting calculations. Additional detail on minimum degree-based sparse matrix ordering is presented in appendix gif.



next up previous
Next: Pseudo-Factorization Up: The Preprocessing Phase Previous: The Preprocessing Phase



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