lsqnonneg improvements

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

lsqnonneg improvements

Jaroslav Hajek-2
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
changes.

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
robust.
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:

generate data:
A = rand(1000,200); x = rand(200,1) - 0.1; b = A*x;
save -ascii A A
save -ascii b b

bench:
load A
load b
tic; x = lsqnonneg (A, b); toc
sum (x)

Octave with above patch:

Elapsed time is 0.603467 seconds.
ans =  75.066

Matlab2007a:

Elapsed time is 39.081721 seconds.

ans =

   75.0662

i.e. 65x faster. Apparently Matlab is using something more simplistic.


cheers

--
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz
Reply | Threaded
Open this post in threaded view
|

Re: lsqnonneg improvements

Bill Denney-5
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
> changes.

Hi Jaroslav,

The original reference is available here (the link should take you
directly to page 161 which has a description of the algorithm):
http://books.google.com/books?id=ROw4hU85nz8C&pg=PA162&lpg=PP161#PPA161,M1

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
(http://www.netlib.org/lawson-hanson/all).

Have a good day,

Bill