Skip to main content
Open Access Publications from the University of California

Combinatorial Algorithms for Computing Column Space Bases That Have Sparse Inverses


This paper presents a combinatorial study on the problem of constructing a sparse basis forthe null-space of a sparse, under determined, full rank matrix, A. Such a null-space is suitable for solving solving many saddle point problems. Our approach is to form a column space basis of A that has a sparse inverse, by selecting suitable columns of A. This basis is then used to form a sparse null-space basis in fundamental form. We investigate three different algorithms for computing the column space basis: Two greedy approaches that rely on matching, and a third employing a divide and conquer strategy implemented with hypergraph partitioning followed by the greedy approach. We also discuss the complexity of selecting a column basis when it is known that a block diagonal basis exists with a small given block size.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View