next up previous
Next: About this document Up: Parallel Choleski Factorization of Previous: Minimum-Degree Ordering

A Node-tearing Example

An example illustrating node-tearing nodal analysis is presented in figures 33 through 36. The example graph, presented in figure 33, has two distinct portions connected at node . Node meets the selection criteria for the first node, and the contour tableau is presented in figure 34. 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 35 illustrates the ordered graph, note that only the labels on the modes have changed from figure 33. To illustrate the effect of ordering the matrix, the matrix sparsity structure for the original and ordered graphs are presented in figure 36. 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 33: Graph for a Node-Tearing Example  

 
Figure 34: Example Contour Tableau 

 
Figure 35: Relabeled Example Graph 

 
Figure 36: Matrix Representation of the Example Graphs 



David P. Koester
Sun Oct 22 15:40:25 EDT 1995