Computing the block triangular form of a sparse matrix

Alex Pothen, Chin-Ju Fan · ACM Transactions on Mathematical Software · 1990

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.

Cited by 385 works. doi:10.1145/98267.98287 Open-access PDF

Authors

References