In many applications, a basis for the null space need not be explicitly represented, but it suffices to choose a basis V for the column space of A. The efficiency of the algorithms using this basis depends on a variety of factors, for example, whether V-1 is sparse, whether V-1 is easy to compute, and whether linear systems involving V are easy to solve. We call the problem of choosing a ``nice'' basis of an under-determined matrix the nice basis problem. Formally, we consider the following problem: Given a sparse, under-determined matrix A with m rows and n columns (and full row rank), choose a set of m columns that forms a column basis for A with some desired ``nice'' property.
We consider several useful combinatorial and numerical properties that make a basis ``nice.'' The combinatorial properties involve the nonzero structure of V (provided V is nonsingular). For example, we consider how to construct V to be as sparse as possible, or block diagonal, or block triangular, both with small blocks. Numerical properties that can guide the choice of V may include diagonal dominance, optimization of various norms of V, and minimization of the condition number of V. This is an ongoing project; our talk will discuss applications of the nice basis problem and present our partial results.