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
- An Efficient Heuristic Procedure for Partitioning Graphs
- Depth-First Search and Linear Graph Algorithms
- Combinatorial optimization: networks and matroids
- Combinatorial Optimization: Algorithms and Complexity.
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Computer Solution of Large Sparse Positive Definite Systems.
- Partitioning Sparse Matrices with Eigenvectors of Graphs
- Direct Methods for Sparse Matrices
- Sparse matrix test problems
- Computer Solution of Large Sparse Positive Definite