The node-tearing-based ordering is designed to isolate both independent blocks and coupling equations within a sparse matrix while minimizing the number of coupling equations by examining the natural structure in the matrix. Tearing here refers to breaking the original problem into smaller sub-problems, whose partial solutions can be combined to give the solution of the original problem. Node-tearing nodal analysis is a specialized form of diakoptic analysis [6] that has been developed especially for power system network analysis [9]. Examples in reference [9] illustrate that this technique also has validity for general structural analysis.
The basic goal of node-tearing analysis is to partition a graph into two arbitrary subsets that contain mutually independent sub-blocks and coupling equations. The tearing optimization problem attempts to minimize the number of elements in the coupling equations over all distinct partitions of sub-matrices and coupling equations while also meeting a constraint that limits the size of any sub-matrix. By modifying this parameter, control can be exercised over the shape of the ordered sparse matrix. When the maximum size of the diagonal blocks is small, then the matrix is nearly in diagonal-bordered form. However, when this value is large, the number of coupling equations decreases as some of these equations are moved into diagonal blocks as smaller diagonal blocks are concatenated. Moreover, this technique can be applied recursively to reduce the bandwidth of the diagonal, except for controlled sized sub-borders. Because both the size of the major and minor blocks are user-selectable, the size of these blocks can be chosen to maximize performance for vector processor implementations.
This graph optimization problem belongs to the family of NP-complete problems, so an efficient heuristic algorithm has been developed, based on examining the contour of the graph [9]. The computational complexity of this algorithm is
due to the fact that all nodes in the graph must be examined and for
each element in the contour tableau, all elements of the adjacency
set, , must be examined for the next node. Because the
matrix is sparse, the maximum number in the adjacency set will be
substantially less than n. Examples of node-tearing-based ordering
are presented in figures 8 and 9 respectively for
maximum diagonal block sizes of 64 and 128 nodes. Figure 10
illustrates a recursive application of node-tearing with maximum block
size of 128 nodes for the larger blocks and maximum size of 16 for the
diagonal sub-blocks within the larger blocks. These examples also use
the BCSPWR09.PSA matrix of the Boeing-Harwell series [4]. The
number of fillin for these ordered matrices is 3,248, 3,486, and 3,838
respectively, with a substantial portion of the fillin occurring in
the lower right-hand corner.
Figure 8: Node-Tearing-Based Ordering --- Maximum Blocksize of 64
Figure 9: Node-Tearing-Based Ordering --- Maximum Blocksize of 128
Figure 10: Recursive Node-Tearing-Based Ordering --- Maximum Blocksizes of 128 and 16
The general performance of node-tearing-based ordering is dependent on the maximum number of nodes in a diagonal block, and the number of processors that the independent sub-matrices are spread over. The number of coupling equations and the size of the last block is dependent only on the maximum number of nodes in a diagonal block, which is illustrated in figure 11. It is desirable to minimize the size of the last block, but this can cause load imbalance as the number of processors increases. Families of curves illustrating load imbalance as a function of the number of processors is presented in figure 12. For all ordering with different size diagonal blocks, there is perfect load-balancing for four processors, however, as the number of processors increases, so does load imbalance.
Figure 11: Node-Tearing --- Nodes in Last Block
Figure 12: Node-Tearing --- Load Imbalance