Computing the block triangular form of a sparse matrix
Open Access
- 1 December 1990
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 16 (4) , 303-324
- https://doi.org/10.1145/98267.98287
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.Keywords
This publication has 20 references indexed in Scilit:
- A graph partitioning algorithm by node separatorsACM Transactions on Mathematical Software, 1989
- Sparse matrix test problemsACM Transactions on Mathematical Software, 1989
- Remarks on implementation of O ( n 1/2 τ) assignment algorithmsACM Transactions on Mathematical Software, 1988
- A parallel graph partitioning algorithm for a message-passing multiprocessorInternational Journal of Parallel Programming, 1987
- Predicting fill for sparse orthogonal factorizationJournal of the ACM, 1986
- On Algorithms for Obtaining a Maximum TransversalACM Transactions on Mathematical Software, 1981
- Solution of sparse linear least squares problems using givens rotationsLinear Algebra and its Applications, 1980
- An Implementation of Tarjan's Algorithm for the Block Triangularization of a MatrixACM Transactions on Mathematical Software, 1978
- Connectivity and Reducibility of GraphsCanadian Journal of Mathematics, 1962
- Coverings of Bipartite GraphsCanadian Journal of Mathematics, 1958