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/6438
Title: The Sparse Null Space Basis Problem
Authors: Coleman, Thomas F.
Pothen, Alex
Keywords: computer science
technical report
Issue Date: Jul-1984
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR84-598
Abstract: The sparse null space basis problem is the following: $A t \times n$ matrix $A (t less than n)$ is given. Find a matrix $N$, with the fewest nonzero entries in it, whose columns span the null space of $A$. This problem arises in the design of practical algorithms for large-scale numerical optimization problems. Surprisingly, this problem can be formulated as a combinatorial optimization problem under a non-degeneracy assumption on $A$. THe theory of matchings in bipartite graphs - marriage theorems - can then be used to obtain the nonzero positions in $N$. Numerically stable matrix factorizations are used in the next phase to compute $N$. We use conformal decompositions to characterize the columns of a sparsest null basis. Matroid theory is used to prove that a greedy algorithm constructs a sparsest null basis. We prove that finding a sparsest null basis is NP-hard by showing that associated matroidal and graph-theoretic problems are NP-complete. We propose two approximation algorithms to construct sparse null bases. Both of them make use of the Dulmage-Mendelsohn decomposition of rectangular matrices. One algorithm is a sparsity exploiting variant of the variable-reduction technique. The second is a locally greedy algorithm that constructs a null basis with an upper triangular submatrix. These results are extended to computing sparse orthogonal null bases. We discuss how this "two-phase" approach can construct sparser null bases than a purely numerical approach; it is also potentially faster than the latter. Finally, we classify all known methods for constructing null bases, and show some unexpected equivalences between some of them.
URI: http://hdl.handle.net/1813/6438
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
84-598.pdf3.93 MBAdobe PDFView/Open
84-598.ps1.03 MBPostscriptView/Open

Refworks Export

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

 

© 2014 Cornell University Library Contact Us