Combinatorial algorithms for computing column space bases that have sparse inverses

zbMATH Open1112.65040MaRDI QIDQ871171FDOQ871171

Authors: Edmond Chow, Alex Pothen, Ali Pinar 

Publication date: 16 March 2007

Published in: ETNA - Electronic Transactions on Numerical Analysis (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/127446

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On the Computation of Null Spaces of Sparse Rectangular Matrices
• Computing a Sparse Basis for the Null Space
• An algorithm to compute a sparse basis of the null space
• The Null Space Problem II. Algorithms
• An application of the Dulmage-Mendelsohn decomposition to sparse null space bases of full row rank matrices

zbMATH Keywords

matchinggreedy algorithmsblock diagonal matrixhypergraph partitioningdivide and conquer strategy, inverse of a basisblock angular matrixsparse column space basissparse null space basis

Mathematics Subject Classification ID

Quadratic programming (90C20) Computational methods for sparse matrices (65F50)

Cited In (8)

• A null-space approach for large-scale symmetric saddle point systems with a small and non zero \((2, 2)\) block
• The Sparse Basis Problem and Multilinear Algebra
• Approximation algorithms in combinatorial scientific computing
• On the Computation of Null Spaces of Sparse Rectangular Matrices
• A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs
• A heuristic to generate rank-1 GMI cuts
• Block computation and representation of a sparse nullspace basis of a rectangular matrix
• A \(2/3\)-approximation algorithm for vertex-weighted matching

This page was built for publication: Combinatorial algorithms for computing column space bases that have sparse inverses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q871171)