A Graph-Based Algorithm for Constrained Partitioning of Sparse Matrices

PONZONI, IGNACIO; SÁNCHEZ, MABEL C.; BRIGNOLE, NÉLIDA B.

Buenos Aires

Congreso; IV WCCM (4th World Congress on Computational Mechanics); 1998

IACM (International Association for Computational Mechanics)

We present a direct method to carry out a structural rearrangement of the occurrence matrix from systems of non-linear equations in order to yield a Block lower-Triangular Form specially adapted to solve problems of plant instrumentation design and revamp. The procedure is based on graph decompositions obtained thanks to a new vertex classification proposed by the authors. The methodology is of general application, also handling structurally singular matrices. An innovative feature within the algorithm is the incorporation of constraints that ensure realistic results. The final decomposition is optimum in the sense that it yields the maximum number of irreducible blocks.