How can one construct a sparse null space basis using recursive LU decomposition? Given an $m$ by $n$ matrix $A$ I'm familiar with the standard method to compute a basis for the null space of $A$ by computing a QR factorization of $A^T$. If $A$ is large and sparse, we can use sparse-QR techniques with pivoting, but the resulting $Q$ matrix (and portion used for the null space basis) may be quite dense.
For simple running example, consider a $n \times 1$ row of ones $A = [1 ... 1]$. This matrix has all zero-average vectors in its null space. If I use (MATLAB's) QR factorization ([Q,R,E] = qr(A');) the resulting $Q$ matrix is a dense $n \times n$ matrix. In this case, we know a sparse basis for the null space exists: 
$N = \left[\begin{array}{c} \begin{array} --1 & -1& \dots & -1\\ \end{array} \\ I \end{array}\right]$, where $I$ is the $n-1 \times n-1$ (sparse) identity matrix.
A preliminary question is, 1) how can one construct a(/the most) sparse null space basis given $A$?
But, actually I have found an algorithm's implementation online by Pawel Kowal* that computes sparse null spaces very well. Trying to trace through the code it seems to work by recursively applying an LU-decomposition with pivoting. However, I can't completely understand what it's doing and certainly don't understand why it's working. The comments and function names say it is computing an "LUQ" decomposition:
function [L,U,Q] = luq(A,do_pivot,tol)
%  PURPOSE: calculates the following decomposition
%             
%       A = L |Ubar  0 | Q
%             |0     0 |
%
%       where Ubar is a square invertible matrix
%       and matrices L, Q are invertible.
%

Is this decomposition well known? Does it go by another name?
This algorithm seems to work very well. In the example above, this decomposition produces the "ideal" sparse basis for the null space $N$.
So my current question, 2) is there a corresponding academic paper describing this method for computing a sparse basis for the null space of a matrix via recursive LU decomposition?
*I've had no luck trying to contact Pawel Kowal for more information.
 A: Not the same algorithm, but here is an alternative that I have used in a recent paper; you can put it together quickly with standard Matlab functions if $A$ is a $m\times n$ matrix with $m\ll n$ (like in your example).
Compute a rank-revealing QR decomposition with [Q,R,E] = qr(A); now $E$ is a permutation matrix, and $A=QRE^T$. Set 
$$
R = \begin{bmatrix}
R_1 & R_2\\
0 & 0
\end{bmatrix},
$$
with $R_1$ square invertible and triangular. Sounds crazy when you think about it, but a matrix can be square and 
triangular at the same time. :)
Now $E \begin{bmatrix}-R_1^{-1}R_2\\ I \end{bmatrix}$ is a basis for the nullspace of $A$ with only $O(mn)$ nonzeros (and you can compute it in time $O(nm^2)$.
If $A$ is full rank, the second block row of zeros is going to be empty. You might need to set a threshold to decide which rows are zero and which are not in that decomposition; but if you want to compute a basis for the nullspace you have to take a numerical decision on its rank whatever you do.
At a first glance, it seems that the algorithm you linked to does something similar, but with a pivoted LU decomposition instead of a QR (which is indeed a better idea if $A$ is sparse in addition to being short and fat).

As for the name of your decomposition, if you don't impose any particular structure on $L,Q$ it could be everything from an SVD to a rank-revealing QR or LU. Probably, though, it is some variant of "rank-revealing LU decomposition"; this term is a good literature pointer to search for alternatives.
