The software implementation to perform node-tearing nodal analysis
utilizes the basic concept of building a contour tableau to identify
independent sub-matrices and the coupling equations in an undirected
graph representing a sparse matrix. In our implementation, the search
for the local minimum of the contour number is limited to within the
range ,
. When an independent sub-matrix is found, this iterating set is
moved into a set
, where
. After the sets
and
are determined, the equations
corresponding to the sets
and
are further ordered using the minimum-degree ordering
algorithm.
Figure 14 illustrates the major steps in the
node-tearing ordering algorithm that produces block-bordered-diagonal
form matrices with minimized fillin. The algorithm examines all nodes
essentially once, where the size of the independent sub-blocks are
limited to . 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. The value of must be less than n, and because the graphs
will be sparse, the maximum number in the adjacency set will be
substantially less than n.
Figure 14: The Node-Tearing Algorithm