Power Systems Diakoptics Analysis based on Node-Tearing-Nodal Analysis

	The node-tearing-based ordering is designed to isolate both
independent blocks and coupling equations within a sparse matrix while
minimizing the number of coupling equations by examining the natural
structure in the matrix.  Tearing here refers to breaking the original
problem into smaller sub-problems, whose partial solutions can be
combined to give the solution of the original problem.  Node-tearing
nodal analysis is a specialized form of diakoptic analysis [1] that
has been developed especially for power system network analysis [2].
Examples in reference [2] illustrate that this technique
also has validity for general structural analysis.

	The basic goal of node-tearing analysis is to partition a
graph into two arbitrary subsets that contain mutually independent
sub-blocks and coupling equations.  The tearing optimization problem
attempts to minimize the number of elements in the coupling equations
over all distinct partitions of sub-matrices and coupling equations
while also meeting a constraint that limits the size of any
sub-matrix.  By modifying this parameter, control can be exercised
over the shape of the ordered sparse matrix.  When the maximum size of
the diagonal blocks is small, then the matrix is nearly in
diagonal-bordered form.  However, when this value is large, the number
of coupling equations decreases as some of these equations are moved
into diagonal blocks as smaller diagonal blocks are concatenated.
Moreover, this technique can be applied recursively to reduce the
bandwidth of the diagonal, except for controlled sized sub-borders.
Because both the size of the major and minor blocks are
user-selectable, the size of these blocks can be chosen to maximize
performance for vector processor implementations.

	Examples of node-tearing-based ordering are presented in GIFs
NT-1.gif through NT-3.gif respectively for maximum diagonal block
sizes of 32, 64, and 128 nodes.  NT-3.gif illustrates a recursive
application of node-tearing with maximum block size of 128 nodes for
the larger blocks and maximum size of 16 for the diagonal sub-blocks
within the larger blocks.  These examples use the BCSPWR09 matrix of
the Boeing-Harwell series [3].  The number of fillin for these ordered
matrices is 2,765, 3,248, 3,486, and 3,838 respectively, with a
substantial portion of the fillin occurring in the lower right-hand
corner.

	The general performance of node-tearing-based ordering is
dependent on the maximum number of nodes in a diagonal block, and the
number of processors that the independent sub-matrices are spread
over.  The number of coupling equations and the size of the last block
is dependent only on the maximum number of nodes in a diagonal block,

References

[1] H. H. Happ: Diakoptics - ``The Solution of System Problems by
    Tearing'': Proceedings of the IEEE, 62(7):930-940: July 1974.

[2] A. Sangiovanni-Vincenntelli, L. K. Chen, and L. O. Chua:
    Node-Tearing-Nodal Analysis: Technical Report ERL-M582, 
    Electronics Research Laboratory, College of Engineering, 
    University of California, Berkley: October 1976.

[3] L. S. Duff, R. G. Grimes, and J. G. Lewis: User's Guide for the
    Harwell-Boeing Sparse Matrix Collection: Technical Report 
    TR/PA/92/86, Boeing Computer Services: (available 
    by anonymous ftp at orion.cerfacs.fr): October 1992.
