Re: improved QR & Cholesky updating

[Jaroslav Hajek]

On Tue, Jan 20, 2009 at 10:58 PM, John W. Eaton <address@hidden> wrote:
> On 20-Jan-2009, Jaroslav Hajek wrote:
>
> | On Sat, Jan 17, 2009 at 9:08 PM, Jaroslav Hajek <address@hidden> wrote:
> | > hi,
> | >
> | > please consider the changeset:
> | > http://artax.karlin.mff.cuni.cz/~hajej2am/ulozna/octave/qrupdate.diff
> | > improving the qrupdate, qrinsert, qrdelete, qrshift, cholupdate,
> | > cholinsert, choldelete, cholshift.
> | >
> | > Summary of changes:
> | > The current version 0 snapshot of qrupdate is deleted from libcruft,
> | > instead qrupdate is a weak dependency.
> | > If found, the above functions are defined, as well as corresponding
> | > methods of QR & CHOL classes in liboctave.
> | > All the updating routines now use more efficient column traversal of
> | > matrices. qrupdate, qrinsert & qrdelete support batch
> | > updating/insertion/deletion of columns (avoids repeated copying of the
> | > matrices).
> | > Maybe most importantly, rank-1 update & column insertion now support
> | > economized factorization.
> | >
> | > This (together with the earlier work) makes Octave significantly more
> | > capable w.r.t. factorization updating than M*b.
> | > Applications are optimization routines (fsolve, lsqnonneg).
> | >
> | > cheers
> | >
> |
> | Changeset applied.
>
> Thanks for doing this work.
>
> I updated and now I see 44 new test failures.  There are 16 in
> chol.cc, 24 in qr.cc, and 4 in fsolve.  The failing tests in chol and
> qr should be modified to use "testif HAVE_QRUPDATE" (or similar) but
> I'm not sure what to do about fsolve.

OK, sorry. I forgot about testif.


> I think it is bad to have
> fsolve not work if the qrupdate library is missing.  Is there a way to
> provide this functionality without the Fortran library (perhaps in a
> sub-optimal way)?

Sorry, this should have been part of the patch, but somehow I forgot
to do the last refresh (also sorry for the message).
It's now uploaded. fsolve will simply check for qrupdate at first
start, and if not found, it will update the qr factorization by
recalculation. For large systems, of course, that's going to be much
slower, but will work.

I intend to do the same thing anywhere the updating routines will be
used (due to their nature, they can be always replaced). That's why I
disabled their compiling entirely when qrupdate is not present - so
that their presence can be checked with the "exist" function.

> Either that, or maybe we should require the
> qrupdate library, in which case it should probably be distributed with
> the Otave sources.
>
> jwe
>

cheers

-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz