Recommendations for a large scale bounded variable least squares (BVLS) solver for sparse matrices

I'm trying to solve the BVLS problem for huge (2e6x2e6) matrices which are very sparse (4 elements per row). Does anybody have a recommendation for a free solver (preferably a library of routines)?

The BVLS problem is defined as:

$\underset{l \le x \le u}{\min} \lVert Ax - b \rVert_2^2$

-
Have you looked at netlib.org? –  Steve Huntsman Jun 10 '10 at 16:08
@Steve: I just looked at it and it provides several useful papers and links. But all the implementations don't seem to discuss sparse matrix support which I truly need. –  Jacob Jun 10 '10 at 16:29
netlib.org/sparse/readme –  Steve Huntsman Jun 10 '10 at 16:37
@Steve: Thanks, but how do I introduce the constraints? –  Jacob Jun 10 '10 at 21:33
It appears you have a QP with simple bounds. There tons of solvers out there for QPs with sparse matrix support. You might want to look into these: abel.ee.ucla.edu/cvxopt, pserc.cornell.edu/bpmpd, control.ee.ethz.ch/~joloef/clp.php, pages.cs.wisc.edu/~swright/ooqp. Or just look here under quadratic programming: users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Solvers.Solvers –  Gilead Aug 13 '10 at 3:28

For a free solver I have found this: http://sourceforge.net/projects/quadprog/ However it assumes that $A$ has full column rank. This is just because this algorithm uses the dual problem which exists when the Hessian $A^TA$ is positive definite.
@Alext87:I use lsqlin for my experiments but I need a solver to integrate into a larger application (and it should be free). The matrix is not full rank, so I don't know about quadprog. –  Jacob Jun 14 '10 at 14:34