Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: The Null Space Problem II: Algorithms
Authors: Coleman, Thomas F.
Pothen, Alex
Keywords: computer science
technical report
Issue Date: Apr-1986
Publisher: Cornell University
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.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
86-747.pdf2.53 MBAdobe PDFView/Open
86-747.ps566.73 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us