  In this work, we develop a fast hierarchical solver for solving large, sparse
least squares problems. We build upon the algorithm, spaQR (sparsified QR),
that was developed by the authors to solve large sparse linear systems. Our
algorithm is built on top of a Nested Dissection based multifrontal QR
approach. We use low-rank approximations on the frontal matrices to sparsify
the vertex separators at every level in the elimination tree. Using a two-step
sparsification scheme, we reduce the number of columns and maintain the ratio
of rows to columns in each front without introducing any additional fill-in.
With this improvised scheme, we show that the runtime of the algorithm scales
as $\mathcal{O}(M \log N)$ and uses $\mathcal{O}(M)$ memory to store the
factorization. This is achieved at the expense of a small and controllable
approximation error. The end result is an approximate factorization of the
matrix stored as a sequence of sparse orthogonal and upper-triangular factors
and hence easy to apply/solve with a vector. Finally, we compare the
performance of the spaQR algorithm in solving sparse least squares problems
with direct multifrontal QR and CGLS iterative method with a standard diagonal
preconditioner.
