The Null Space Problem II. Algorithms
Thomas F. Coleman, Alex Pothen · SIAM Journal on Algebraic and Discrete Methods · 1987
The null space problem is that of finding a sparsest basis for the null space (null basis) of an underdetermined matrix. This problem was shown to be NP-hard in Coleman and Pothen (this Journal, 7 (1986), pp. 527–537). In this paper we develop heuristic algorithms to find sparse null bases. A basis is computed by columns, i.e., by finding a null vector linearly independent of those previously obtained. The algorithms to compute null vectors 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, nonzero coefficients in the null vector are computed from this dependent set. We have designed two algorithms: the first computes a fundamental basis (one with an embedded identity matrix), and the other, a triangular basis (one with an upper triangular matrix). We describe implementations of our algorithms and provide computational results on several large sparse constraint matrices from linear programs. Both algorithms find null bases which are quite sparse, have low running times, and require small intermediate storage. The triangular algorithm finds sparser bases at the expense of greater running times. We believe that this algorithm is an attractive candidate for large sparse null basis computations.