hi Bill,

please take notice of the changeset

http://hg.savannah.gnu.org/hgweb/octave/rev/a6c1aa6f5915that 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