Skip to main content


eCommons@Cornell

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

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6587
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
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-747
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.
URI: http://hdl.handle.net/1813/6587
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