A detailed theoretical derivation of node-tearing is too lengthy to describe here in rigorous mathematical terms. We refer interested readers to references [10,13] for proofs of the mathematics, although a brief description of node-tearing follows.
Let the set denote the nodes of a graph
and let
denote the edges in
, or
. In summary, node-tearing is a greedy algorithm that
partitions the nodes
in
into
where: ¯Mutual independence occurs when no edges in
is the set of nodes in the mutually independent partitions
is the set of nodes in a mutually independent partition
is the set of nodes in the coupling equations
In addition to ordering matrices into block-diagonal-bordered form
using node-tearing, we require that the number of coupling equations,
, is minimized over all distinct partitions
of
while also specifying
that
,
. This
constraint permits some control of the maximum size of diagonal
blocks,
, which can prove quite useful when tearing a graph
for solving on multi-processors. By modifying this parameter, control
can be exercised over the shape of the ordered sparse matrix ---
yielding small blocks when
is small and limiting the size
of the borders in a block-diagonal-bordered matrix when
is
large. This optimization problem belongs to the family of NP-complete
problems
[13], so a simple, efficient heuristic algorithm has been
developed based on examining the contour of the graph [13].
A contour-tableau contains three lists:
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
. Figure 4 illustrates the major steps in the
node-tearing ordering algorithm. 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 4: The Node-Tearing Algorithm