We consider the problem of permuting the rows and columns of a rectangular or square, unsymmetric sparse matrix to compute its block triangular form. This block triangular form is based on a canonical decomposition of bipartite graphs induced by a maximum matching and was discovered by Dulmage and Mendelsohn. We describe implementations of algorithms to compute the block triangular form and provide computational results on sparse matrices from test collections. Several applications of the block triangular form are also included.
Description
Computing the block triangular form of a sparse matrix
%0 Journal Article
%1 pothen90
%A Pothen, Alex
%A Fan, Chin-Ju
%C New York, NY, USA
%D 1990
%I ACM
%J ACM Trans. Math. Softw.
%K dulmage-mendelsohn graph.theory linear.algebra matrix numerical.analysis
%N 4
%P 303--324
%R 10.1145/98267.98287
%T Computing the Block Triangular Form of a Sparse Matrix
%V 16
%X We consider the problem of permuting the rows and columns of a rectangular or square, unsymmetric sparse matrix to compute its block triangular form. This block triangular form is based on a canonical decomposition of bipartite graphs induced by a maximum matching and was discovered by Dulmage and Mendelsohn. We describe implementations of algorithms to compute the block triangular form and provide computational results on sparse matrices from test collections. Several applications of the block triangular form are also included.
@article{pothen90,
abstract = {We consider the problem of permuting the rows and columns of a rectangular or square, unsymmetric sparse matrix to compute its block triangular form. This block triangular form is based on a canonical decomposition of bipartite graphs induced by a maximum matching and was discovered by Dulmage and Mendelsohn. We describe implementations of algorithms to compute the block triangular form and provide computational results on sparse matrices from test collections. Several applications of the block triangular form are also included.},
acmid = {98287},
added-at = {2017-04-08T10:54:46.000+0200},
address = {New York, NY, USA},
author = {Pothen, Alex and Fan, Chin-Ju},
biburl = {https://www.bibsonomy.org/bibtex/29ab974a286a2c50122eba8f6af098727/ytyoun},
description = {Computing the block triangular form of a sparse matrix},
doi = {10.1145/98267.98287},
interhash = {8fed9ed30a82596431abdd67f7c2b839},
intrahash = {9ab974a286a2c50122eba8f6af098727},
issn = {0098-3500},
issue_date = {Dec. 1990},
journal = {ACM Trans. Math. Softw.},
keywords = {dulmage-mendelsohn graph.theory linear.algebra matrix numerical.analysis},
month = dec,
number = 4,
numpages = {22},
pages = {303--324},
publisher = {ACM},
timestamp = {2017-04-08T10:54:46.000+0200},
title = {Computing the Block Triangular Form of a Sparse Matrix},
volume = 16,
year = 1990
}