next up previous
Next: The Node-Tearing Implementation Up: Node-Tearing Nodal Analysis Previous: The Node-Tearing Algorithm

An Example of Node-Tearing

An example illustrating node-tearing nodal analysis is presented in figures gif through gif. The example graph, presented in figure gif, has two distinct portions connected at node . Node meets the selection criteria for the first node, and the contour tableau is presented in figure gif. There is a distinct local minimum in the contour number at which identifies node as the node that couples the two mutually independent graph partitions. Figure gif presents the ordered graph --- note that only the labels on the modes have changed from figure gif. To illustrate the effect of ordering the matrix, the matrix sparsity structure for the original and ordered graphs are presented in figure gif. In these figures, original data values are represented with + symbols while fillin are denoted with F characters. Within the subgraphs, the values would be ordered with a minimum-degree ordering algorithm. For this sample matrix, minimum degree ordering for the entire matrix would yield the same results.

Figure gif completes this example by illustrating the elimination tree for this example. For the unordered matrix, there are no branches in the elimination tree; consequently, if calculations are performed in the original order, there would be no factorization operations that could be performed in parallel. However, after ordering there is available parallelism denoted by the multiple leaf supernodes in the elimination tree.

 
Figure: Graph for a Node-Tearing Example  

 
Figure: Example Contour Tableau 

 
Figure: Relabeled Example Graph 

 
Figure: Matrix Representation of the Example Graphs 

 
Figure: Elimination Trees for the Example Graphs 



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