Computing the block triangular form of a sparse matrix

DOI10.1145/98267.98287zbMath0900.65117MaRDI QIDQ4371656

Alex Pothen, Chin-Ju Fan

Publication date: 9 February 1998

Published in: ACM Transactions on Mathematical Software (Search for Journal in Brave)

Full work available at URL: http://www.acm.org/pubs/contents/journals/toms/1990-16/

zbMATH Keywords

algorithms; bipartite graphs; maximum matchings; Dulmage-Mendelsohn decomposition

Mathematics Subject Classification ID

65F50: Computational methods for sparse matrices

Related Items

A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs, An ADMM-based interior-point method for large-scale linear programming, A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs, Diagnosis of Partially Observed Petri Net Based on Analytical Redundancy Relationships, Approximation algorithms in combinatorial scientific computing, Controllability of Coupled Parabolic Systems with Multiple Underactuations, Part 1: Algebraic Solvability, DAESA—A Matlab Tool for Structural Analysis of Differential-Algebraic Equations, Unnamed Item, A survey of direct methods for sparse linear systems, First-order chemical reaction networks. I: Theoretical considerations, On bounded block decomposition problems for under-specified systems of equations, Local null controllability of the three-dimensional Navier-Stokes system with a distributed control having two vanishing components, Efficient index reduction algorithm for large scale systems of differential algebraic equations, Matchings, covers, and Jacobian matrices, On the row merge tree for sparse LU factorization with partial pivoting, Predicting the structure of sparse orthogonal factors, A clustering heuristic to detect staircase structures in large scale linear programming models, Using domain decomposition to find graph bisectors, Patterns that preserve sparsity in orthogonal factorization, A distance constrained synaptic plasticity model of \textit{C. elegans} neuronal network, From structural analysis to observer-based residual generation for fault detection, A geometric framework for sparse matrix problems, An efficient method for determining fault isolability properties based on an augmented system model, Index reduction of differential algebraic equations by differential Dixon resultant, A manifold-based approach to sparse global constraint satisfaction problems, A \(2/3\)-approximation algorithm for vertex-weighted matching, Scaling matrices and counting the perfect matchings in graphs, Preconditioners for rank deficient least squares problems, Distributed algebraic tearing and interconnecting techniques, Updating preconditioners for modified least squares problems, A robust approach for finding all well-separated solutions of sparse systems of nonlinear equations, Constrained Min-Cut Replication for K-Way Hypergraph Partitioning, DECOMPOSITION OF GEOMETRIC CONSTRAINT SYSTEMS: A SURVEY, Exploiting Block Triangular form for Solving DAEs: Reducing the Number of Initial Values, A Method for Sensor Placement Taking into Account Diagnosability Criteria