Ordering symmetric sparse matrices is simply renumbering the nodes in the graph to modify characteristics of the corresponding matrix [3]. The computational expense of sparse matrix ordering is not unique to block-diagonal-bordered linear solvers, because all sparse linear solvers must consider ordering to minimize fillin [3].
Our research is examining ordering techniques that:
To transform a sparse matrix into block-diagonal-bordered form requires ordering techniques that efficiently identify mutually independent sub-matrices and coupling equations while also minimizing fillin. Fillin are values that become non-zero when factoring the matrix. For symmetric matrices, like power systems network admittance matrices, a graph-theoretical interpretation for independent sub-matrices exists: independent sub-matrices simply have no directly shared edges in their undirected graph. A simple example with four independent portions of the graph connected by nodes that form the couplings equations is presented in figure 2. No subgraph element has edges to any portion of the graph other than within the local subgraph or connecting to the coupling equations.
Figure 2: Graph with Four Independent Sub-Matrices
In addition to ordering the matrix into block-diagonal-bordered form, load balancing is required in the preprocessing phase. Due to the poor correlation of the size of independent sparse diagonal blocks with the workload, the actual number of calculations in each independent block must be determined in a pseudo factorization step during preprocessing. It is possible to load balance nearly all steps in the factorization of block-diagonal-bordered sparse matrices, except the communications step. Communications are regular with long messages, however, the length of these messages and the corresponding updates within the last block, may vary between processors.
The preprocessing phase required for efficient factorization of block-diagonal-bordered form will be more computationally intensive than the simple algorithms required to prepare a matrix for numerical factorization presented in the recent literature. In the two techniques presented below that order sparse matrices into block-diagonal-bordered form, each has two phases. First, the independent sub-matrices are identified and then the matrix is ordered with this additional constraint to minimize resulting fillin. The additional processing requirements for these steps limit the applicability of this technique to repetitive solutions of static network structures, where the additional effort can be amortized over multiple solutions of similar linear systems. Because the sparse matrices from power system applications are representative of actual physical power distribution networks, the sparse matrices in load-flow analysis and power system transient stability analysis remain static over time periods significantly greater than required to recalculate new orderings. The computational expense of each ordering can be amortized over many applications of the block-diagonal-bordered linear solver.