next up previous contents
Next: About this document Up: Parallel Direct Methods for Previous: Minimum-Degree Ordering

A Node-tearing Example

An example illustrating node-tearing nodal analysis is presented in figures 64 through 67. The example graph, presented in figure 64, has two distinct portions connected at node . Node meets the selection criteria for the first node, and the contour tableau is presented in figure 65. 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 66 illustrates the ordered graph, note that only the labels on the modes have changed from figure 64. To illustrate the effect of ordering the matrix, the matrix sparsity structure for the original and ordered graphs are presented in figure 67. In these figures, original data values are represented with + symbols while fillin are denoted with F characters. Within the sub-blocks, 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 64: Graph for a Node-Tearing Example  

 
Figure 65: Example Contour Tableau 

 
Figure 66: Relabeled Example Graph 

 
Figure 67: Matrix Representation of the Example Graphs 



David P. Koester
Sun Oct 22 15:31:10 EDT 1995