The Null Space Problem II. Algorithms
Authors:
- Thomas F. ColemanTCThomas F. Coleman
- Alex PothenAPAlex Pothen
- 1 October 1987
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 8 (4) , 544-563
Abstract
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.Keywords
This publication has 16 references indexed in Scilit:
- Computing a Sparse Basis for the Null SpaceSIAM Journal on Algebraic Discrete Methods, 1987
- The Null Space Problem I. ComplexitySIAM Journal on Algebraic Discrete Methods, 1986
- Predicting fill for sparse orthogonal factorizationJournal of the ACM, 1986
- An algorithm to compute a sparse basis of the null spaceNumerische Mathematik, 1985
- Estimation of sparse hessian matrices and graph coloring problemsMathematical Programming, 1984
- Estimation of Sparse Jacobian Matrices and Graph Coloring BlemsSIAM Journal on Numerical Analysis, 1983
- Algorithms for Generating Fundamental Cycles in a GraphACM Transactions on Mathematical Software, 1982
- On Algorithms for Obtaining a Maximum TransversalACM Transactions on Mathematical Software, 1981
- Graph Theory with Applications1976
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973