Combinatorial algorithms for computing column space bases that have sparse inverses

zbMATH Open1112.65040MaRDI QIDQ871171FDOQ871171

Alex Pothen, Edmond Chow, 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.)

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 (6)

• 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
• A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs
• A heuristic to generate rank-1 GMI cuts
• A \(2/3\)-approximation algorithm for vertex-weighted matching

   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 👍 👎
• Title not available (Why is that?) 👍 👎

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)