“Permutation of Sparse Matrices to a Specific Lower BTF using Graph Decompositions”

I. PONZONI; M.C. SANCHEZ; B. BRIGNOLE

SADIO Electronic Journal on Informatics and Operations Research

SADIO

Año: 1998 p. 76 - 87

A new partitioning algorithm that permutes sparse matrices to a specific block lowertriangularform (BlTF) complying with special features required for instrumentation problems ispresented. The proposal consists in the decomposition of the occurrence matrix in two stages,using methodologies based on graph theory. First of all, Hopcroft-Karp´s algorithm is employedto match the vertices, this classification being carried out by means of a modification ofDulmage-Mendelsohn´s technique, which was devised by the authors. The second step is theapplication of Tarjan´s algorithm to the square blocks obtained as a result of the first stage.