please take notice of the changeset
http://hg.savannah.gnu.org/hgweb/octave/rev/a6c1aa6f5915 that finishes my performance improvements to lsqnonneg.
Since it was you who contributed the original information, and I lack
the access to the cited source, I'd appreciate your review of the
Summary of changes:
The linear problem in each step is solved using Octave's \ operator.
The empty columns are left out of the matrix for greater speed
and also to avoid singularity warnings. The loopback check to delete
vars from P avoids checking for computed zeros to be more
If lsqnonneg detects an overdetermined or square system on entry, it
forms and updates a QR factorization of the positive matrix
using qrinsert/qrdelete, using it to efficiently solve the positive
system in each iteration. After the loop is terminated using the QR
updating, it is restarted without the updating to account on possible
error accumulation during the updating.
A quick benchmark against Matlab:
A = rand(1000,200); x = rand(200,1) - 0.1; b = A*x;
save -ascii A A
save -ascii b b
tic; x = lsqnonneg (A, b); toc
Octave with above patch:
Elapsed time is 0.603467 seconds.
ans = 75.066
Elapsed time is 39.081721 seconds.
i.e. 65x faster. Apparently Matlab is using something more simplistic.
RNDr. Jaroslav Hajek
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
Jaroslav Hajek wrote:
> hi Bill,
> please take notice of the changeset
> http://hg.savannah.gnu.org/hgweb/octave/rev/a6c1aa6f5915 > that finishes my performance improvements to lsqnonneg.
> Since it was you who contributed the original information, and I lack
> the access to the cited source, I'd appreciate your review of the
I think that it looks fine, though I will admit that I've had to write
this algorithm several times over the years and have found that bugs are
easy to write into here. So after doing the first test (which I can do
with pencil and paper), I usually rely on external tests like you did
using either Matlab or the netlib implementation as a reference