1
$\begingroup$

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$

$\endgroup$
5

1 Answer 1

2
$\begingroup$

This is such a well-solved problem that there are many software packages that have built in functions for this.

Here are a selection of built-in functions in different software packages that can be used:

In Matlab: lsqlin (type help lsqlin into Matlab and it tells you exactly what to type. I have just (approximately) solved your problem with random sparse matrices and it works great.)

KNITRO for Mathematica this package also solves this exact problem but I don't have this software so I can't tell you which exact function.

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.

$\endgroup$
1
  • $\begingroup$ @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. $\endgroup$
    – Jacob
    Jun 14, 2010 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.