Permutation of Sparse Matrices to a Specific Lower BTF using Graph Decompositions
Keywords:
graph theory, directed graphs, bipartite graphs, sparse matrices, block lower-triangular forms, assignment algorithms, partitioning algorithmsAbstract
A new partitioning algorithm that permutes sparse matrices to a specific block lower-triangular form (BlTF) complying with special features required for instrumentation problems is presented. 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 employed to match the vertices, this classification being carried out by means of a modification of Dulmage-Mendelsohn´s technique, which was devised by the authors. The second step is the application of Tarjan´s algorithm to the square blocks obtained as a result of the first stage.
Downloads
Published
Issue
Section
License
Copyright (c) 1998 Ignacio Ponzoni, Mabel C. Sánchez, Nélida B. Brignole
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Those authors who have publications with this journal, agree with the following terms:
a. Authors will retain its copyright and will ensure the rights of first publication of its work to the journal, which will be at the same time subject to the Creative Commons Atribución-NoComercial-CompartirIgual 4.0 Internacional (CC BY-NC-SA 4.0) allowing third parties to share the work as long as the author and the first publication on this journal is indicated.
b. Authors may elect other non-exclusive license agreements of the distribution of the published work (for example: locate it on an institutional telematics file or publish it on an monographic volume) as long as the first publication on this journal is indicated,
c. Authors are allowed and suggested to disseminate its work through the internet (for example: in institutional telematics files or in their website) before and during the submission process, which could produce interesting exchanges and increase the references of the published work. (see The effect of open Access)
