next up previous
Next: Graph Coloring Up: A Parallel Gauss-Seidel Algorithm Previous: Ordering the Last

Node-tearing Nodal Analysis

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: ¯

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

Mutual independence occurs when no edges in are connected to edges in and . Consequently, has no edges in common with , , and there are no edges directly interconnecting any nodes in and , . Connectivity between and , , is indirect and must go through nodes in .

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:

  1. the iterating sets or the potential elements of a set of nodes in the sub-graph ,
  2. the adjacency sets or the set of nodes adjacent to, but not including any elements in the corresponding iterating set,
  3. contour numbers or the cardinality of the adjacency set.
As we perform node-tearing, we want to minimize the size of the adjacency set, , for each partition and subsequently this will minimize . A separate contour-tableau is developed for each diagonal block.

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 



next up previous
Next: Graph Coloring Up: A Parallel Gauss-Seidel Algorithm Previous: Ordering the Last



David P. Koester
Sun Oct 22 15:29:26 EDT 1995