The Null Space Problem II: Algorithms

Abstract

The Null Space Problem is that of finding a sparsest basis for the null space (null basis) of a $t \times n$ matrix of rank $t$. This problem was shown to be NP-hard in Coleman and Pothen (1985). In this paper we develop heuristic algorithms to find sparse null bases. These algorithms have two phases: In the first combinatorial phase, a minimal dependent set of columns is identified by finding a matching in the bipartite graph of the matrix. In the second numerical phase, a null vector is computed from this dependent set. We describe an implementation of our algorithms and provide computational results on several large sparse constraint matrices from linear programs. One of our algorithms compares favorably with previously reported algorithms in sparsity of computed null bases and in running times. Unlike the latter, our algorithm does not require any intermediate dense matrix storage. This advantage should make our algorithm an attractive candidate for large sparse null basis computations. A matching based algorithm is designed to find orthogonal null bases, but we present some theoretical evidence that such bases are unlikely to be sparse. Finally, we show how sparsest orthogonal null bases may be found for an $n$-vector and a $t \times n$ dense matric by a divide and conquer strategy. The algorithm for a dense matrix is suited for implementation on a parallel machine architecture.