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

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

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)

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

Cited in

(8)

• The Sparse Basis Problem and Multilinear Algebra
• Block computation and representation of a sparse nullspace basis of a rectangular matrix
• A null-space approach for large-scale symmetric saddle point systems with a small and non zero \((2, 2)\) block
• 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
• A heuristic to generate rank-1 GMI cuts
• A 2/3-approximation algorithm for vertex weighted matching in bipartite graphs

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)