Hello all,

I am trying to find a way to solve linear systems Ax=b with A sparse (and quite large, up to 1m x 1m) and rectangular (overconstrained system -> i want the least square solution). I had a look at superLU and umfpack and they are both limited to square matrices (actually umfpack can factorize rectangular matrices but not solve rectangular systems).

Does anyone have an idea/know a C/C++ library capable of doing that?

I am thinking that by performing SVD it might be possible but I don't know any library doing SVD on sparse matrices...

Cheers

If you have a very kind matrix, you can always solve the normal equations (A'Ax = A'b) by LU factorization (but this system basically has the squared condition number of A).

A common way is to do a QR factorization of A. Eigen has an implementation of sparse QR, but I think it's designed to do an incomplete factorization as a preconditioner for an iterative solver, and thus might not be very good at completely factorizing A (?)

For very large and very sparse systems, direct factorization is often not feasible. In this case you need to find an iterative solver.

Actually, Eigen does not have any sparse QR yet. A very good GPL implementation is available there:

http://www.cise.ufl.edu/research/sparse/SPQR/