lsqnonneg improvements

[Jaroslav Hajek]

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