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