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:  Jul1984 
Publisher:  Cornell University 
Citation:  http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR84598 
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 largescale numerical optimization problems. Surprisingly, this problem can be formulated as a combinatorial optimization problem under a nondegeneracy 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 NPhard by showing that associated matroidal and graphtheoretic problems are NPcomplete. We propose two approximation algorithms to construct sparse null bases. Both of them make use of the DulmageMendelsohn decomposition of rectangular matrices. One algorithm is a sparsity exploiting variant of the variablereduction 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 "twophase" 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

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