Lawrence Berkeley National Laboratory

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.