improved QR & Cholesky updating

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

improved QR & Cholesky updating

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

--
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: improved QR & Cholesky updating

David Bateman-2
Jaroslav Hajek wrote:
> 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).
>  

Hey maybe you should release it under the LGPL so that Matlab can profit
from it too...... I'm kidding of cause, but only slightly as Tim Davis,
of SuiteSparse, writes under the GPL  and then licenses his code to
Matlab under a different license with I presume renumeration for himself.

D.

--
David Bateman                                [hidden email]
35 rue Gambetta                              +33 1 46 04 02 18 (Home)
92100 Boulogne-Billancourt FRANCE            +33 6 72 01 06 33 (Mob)

Reply | Threaded
Open this post in threaded view
|

Re: improved QR & Cholesky updating

Jaroslav Hajek-2
On Sat, Jan 17, 2009 at 10:03 PM, David Bateman <[hidden email]> wrote:
> Jaroslav Hajek wrote:
>>
>> 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).
>>
>
> Hey maybe you should release it under the LGPL so that Matlab can profit
> from it too...... I'm kidding of cause,

Then, it's pointless to refer you to the usual why-not-LGPL...

> but only slightly as Tim Davis, of
> SuiteSparse, writes under the GPL  and then licenses his code to Matlab
> under a different license with I presume renumeration for himself.
>

That's an interesting point. If, in future, MathWorks will ask for a
commercial license, I suppose they will get it - commercial revenue
from research activities is always welcome by VZLU. But I will
certainly insist on further development under GPL.

Even now I suppose the library is sort of unique functionality, at
least in the free software world, and I plan to address also QRZ
(complete orthogonal) factorization - for underdetermined problems and
GQR for GLM problems, and possibly SVD (that's a different beast,
however). Maybe even sparse factorizations could eventually be
supported.

--
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: improved QR & Cholesky updating

Jaroslav Hajek-2
In reply to this post by Jaroslav Hajek-2
On Sat, Jan 17, 2009 at 9:08 PM, Jaroslav Hajek <[hidden email]> 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.

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: improved QR & Cholesky updating

John W. Eaton
Administrator
On 20-Jan-2009, Jaroslav Hajek wrote:

| On Sat, Jan 17, 2009 at 9:08 PM, Jaroslav Hajek <[hidden email]> 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.  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)?  Either that, or maybe we should require the
qrupdate library, in which case it should probably be distributed with
the Otave sources.

jwe
Reply | Threaded
Open this post in threaded view
|

Re: improved QR & Cholesky updating

Jaroslav Hajek-2
On Tue, Jan 20, 2009 at 10:58 PM, John W. Eaton <[hidden email]> wrote:

> On 20-Jan-2009, Jaroslav Hajek wrote:
>
> | On Sat, Jan 17, 2009 at 9:08 PM, Jaroslav Hajek <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: improved QR & Cholesky updating

John W. Eaton
Administrator
On 21-Jan-2009, Jaroslav Hajek wrote:

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

Instead of

  persistent have_qrupdate = exist ('qrupdate') == 5;

  [...]

  ## Update the QR factorization.
  if (have_qrupdate)
    [q, r] = qrupdate (q, r, u, v);
  else
    [q, r] = qr (q*r + u*v');
  endif

in fsolve.m and every other function that might use qrupdate, why not
check HAVE_QRUPDATE in the QR::update functions and do this operation
there?  Then the check would only have to occur in one place rather
than in every part of Octave that uses qrupdate.

jwe
Reply | Threaded
Open this post in threaded view
|

Re: improved QR & Cholesky updating

Jaroslav Hajek-2
On Wed, Jan 21, 2009 at 4:21 PM, John W. Eaton <[hidden email]> wrote:

> On 21-Jan-2009, Jaroslav Hajek wrote:
>
> | 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.
>
> Instead of
>
>  persistent have_qrupdate = exist ('qrupdate') == 5;
>
>  [...]
>
>  ## Update the QR factorization.
>  if (have_qrupdate)
>    [q, r] = qrupdate (q, r, u, v);
>  else
>    [q, r] = qr (q*r + u*v');
>  endif
>
> in fsolve.m and every other function that might use qrupdate, why not
> check HAVE_QRUPDATE in the QR::update functions and do this operation
> there?  Then the check would only have to occur in one place rather
> than in every part of Octave that uses qrupdate.
>
> jwe
>

I'm not really sure. The point is that in this way, you have, in an
m-file, a clear indication that the qrupdate funcs are unavailable.
Sometimes there may be better workarounds. For instance, the fix I
committed to fsolve is really simplistic; in fact, if qrupdate is not
available, it is better to not form the qr factorization explicitly at
all and simply pass the original jacobian to __dogleg__. This is
something I want to do eventually.
A similar case is lsqnonneg. The current code forms and solves a
system in each step; I'd like to allow it to form a qr or cholesky
factorization once and update it; however, if the updating functions
are not available, then the current code is better than what would
result from replacing the factorizations.

I think this rule applies in general - IMHO, if a functionality is not
available, it's better to disable a function than to provide a version
that always fails, because the former condition can be checked
gracefully and allows for possible workarounds.

regards

--
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: improved QR & Cholesky updating

John W. Eaton
Administrator
On 21-Jan-2009, Jaroslav Hajek wrote:

| I'm not really sure. The point is that in this way, you have, in an
| m-file, a clear indication that the qrupdate funcs are unavailable.

I'd rather not scatter a lot of these checks all around the sources
if we don't have to.  So what if it is suboptimal if the calculation
can be done and the code in the .m files is cleaner?  If you want the
better performance, then install the library that provides it.

| Sometimes there may be better workarounds. For instance, the fix I
| committed to fsolve is really simplistic; in fact, if qrupdate is not
| available, it is better to not form the qr factorization explicitly at
| all and simply pass the original jacobian to __dogleg__. This is
| something I want to do eventually.

Is it ever better to do that if qrupdate is available?  If so, then
I think this feature should be selected via an option, and not because
qrupdate is or is not available.

| I think this rule applies in general - IMHO, if a functionality is not
| available, it's better to disable a function than to provide a version
| that always fails, because the former condition can be checked
| gracefully and allows for possible workarounds.

Doesn't try/catch also allow you to perform a check for functionality
if you really must do it?

Maybe we should improve the error messages for the missing functions
as well.  Instead of just saying "foo: not available in this version
of Octave" we should say "foo: not available because libfoo was not
present when Octave was compiled".  Then maybe having the error makes
more sense, because it tells users why the function is missing.
Otherwise, they just think Octave sucks because it doesn't have the
function they are trying to use.

jwe
Reply | Threaded
Open this post in threaded view
|

Re: improved QR & Cholesky updating

Jaroslav Hajek-2
On Wed, Jan 21, 2009 at 7:35 PM, John W. Eaton <[hidden email]> wrote:

> On 21-Jan-2009, Jaroslav Hajek wrote:
>
> | I'm not really sure. The point is that in this way, you have, in an
> | m-file, a clear indication that the qrupdate funcs are unavailable.
>
> I'd rather not scatter a lot of these checks all around the sources
> if we don't have to.  So what if it is suboptimal if the calculation
> can be done and the code in the .m files is cleaner?  If you want the
> better performance, then install the library that provides it.
>
> | Sometimes there may be better workarounds. For instance, the fix I
> | committed to fsolve is really simplistic; in fact, if qrupdate is not
> | available, it is better to not form the qr factorization explicitly at
> | all and simply pass the original jacobian to __dogleg__. This is
> | something I want to do eventually.
>
> Is it ever better to do that if qrupdate is available?  If so, then
> I think this feature should be selected via an option, and not because
> qrupdate is or is not available.
>
> | I think this rule applies in general - IMHO, if a functionality is not
> | available, it's better to disable a function than to provide a version
> | that always fails, because the former condition can be checked
> | gracefully and allows for possible workarounds.
>
> Doesn't try/catch also allow you to perform a check for functionality
> if you really must do it?

True, but it doesn't catch a warning, does it?

>
> Maybe we should improve the error messages for the missing functions
> as well.  Instead of just saying "foo: not available in this version
> of Octave" we should say "foo: not available because libfoo was not
> present when Octave was compiled".  Then maybe having the error makes
> more sense, because it tells users why the function is missing.
> Otherwise, they just think Octave sucks because it doesn't have the
> function they are trying to use.
>

OK, so where should the replacements go?
Putting them in the QR & Cholesky classes means writing replacement
code for 4 * 8 + 4 * 5 = 52 methods (OK, In fact only quarter and then
copy-paste-search-replace-adjust). I suppose writing generic
replacements directly in the DLD funcs would be simpler. Also, I'm
thinking of issuing a warning the first time any of the updating
function is run, only once.

What do you think?

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: improved QR & Cholesky updating

John W. Eaton
Administrator
On 21-Jan-2009, Jaroslav Hajek wrote:

| True, but it doesn't catch a warning, does it?

Are there cases where missing functions only generate warnings?

| OK, so where should the replacements go?
| Putting them in the QR & Cholesky classes means writing replacement
| code for 4 * 8 + 4 * 5 = 52 methods (OK, In fact only quarter and then
| copy-paste-search-replace-adjust). I suppose writing generic
| replacements directly in the DLD funcs would be simpler. Also, I'm
| thinking of issuing a warning the first time any of the updating
| function is run, only once.
|
| What do you think?

I think the best place is in the QR::update method (for example),
because that way, any code that might use that class won't have to
work around missing functionality either.  Can templates or macros
help here?

jwe
Reply | Threaded
Open this post in threaded view
|

Re: improved QR & Cholesky updating

Jaroslav Hajek-2
On Wed, Jan 21, 2009 at 8:41 PM, John W. Eaton <[hidden email]> wrote:
> On 21-Jan-2009, Jaroslav Hajek wrote:
>
> | True, but it doesn't catch a warning, does it?
>
> Are there cases where missing functions only generate warnings?
>

Not really missing. What I meant is that after I fix this issue,
without qrupdate the functions will be present but sub-optimal. Maybe
some code will want to detect the situation. Now that I think of it,
how does "testif" detect that HAVE_QRUPDATE has been defined? Can this
be done directly from an m-file? If yes, then the above last argument
is dead...

> | OK, so where should the replacements go?
> | Putting them in the QR & Cholesky classes means writing replacement
> | code for 4 * 8 + 4 * 5 = 52 methods (OK, In fact only quarter and then
> | copy-paste-search-replace-adjust). I suppose writing generic
> | replacements directly in the DLD funcs would be simpler. Also, I'm
> | thinking of issuing a warning the first time any of the updating
> | function is run, only once.
> |
> | What do you think?
>
> I think the best place is in the QR::update method (for example),
> because that way, any code that might use that class won't have to
> work around missing functionality either.  Can templates or macros
> help here?
>

OK. I originally considered rebasing QR & CHOL classes on a common
templated ancestor, but eventually I realized there was really not
that much code to share, as most methods are relatively thin wrappers
for the Fortran ones.
Still I can write a .cc file containing the replacement templates and
use that even in the current code.

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: improved QR & Cholesky updating

John W. Eaton
Administrator
On 21-Jan-2009, Jaroslav Hajek wrote:

| Not really missing. What I meant is that after I fix this issue,
| without qrupdate the functions will be present but sub-optimal. Maybe
| some code will want to detect the situation. Now that I think of it,
| how does "testif" detect that HAVE_QRUPDATE has been defined? Can this
| be done directly from an m-file? If yes, then the above last argument
| is dead...

It's a bit of a kluge:

  if (isempty (findstr (octave_config_info ("DEFS"), __feat{1}{1})))

For "testif HAVE_QRUPDATE", __feat{1}{1} would be HAVE_QRUPDATE.

If you think this would be a useful thing to be able to check for
generally, then I think we should have a separate function for this,
and maybe make it work more reliably than just using findstr on the
value returned by octave_config_info ("DEFS").

I can see where some feature checks like this might be useful, but I
still think it would be best to avoid having very many checks of this
kind in the Octave sources if possible.

| OK. I originally considered rebasing QR & CHOL classes on a common
| templated ancestor, but eventually I realized there was really not
| that much code to share, as most methods are relatively thin wrappers
| for the Fortran ones.
| Still I can write a .cc file containing the replacement templates and
| use that even in the current code.

OK.

Thanks,

jwe
Reply | Threaded
Open this post in threaded view
|

Re: improved QR & Cholesky updating

Jaroslav Hajek-2
On Wed, Jan 21, 2009 at 8:58 PM, John W. Eaton <[hidden email]> wrote:

> On 21-Jan-2009, Jaroslav Hajek wrote:
>
> | Not really missing. What I meant is that after I fix this issue,
> | without qrupdate the functions will be present but sub-optimal. Maybe
> | some code will want to detect the situation. Now that I think of it,
> | how does "testif" detect that HAVE_QRUPDATE has been defined? Can this
> | be done directly from an m-file? If yes, then the above last argument
> | is dead...
>
> It's a bit of a kluge:
>
>  if (isempty (findstr (octave_config_info ("DEFS"), __feat{1}{1})))
>
> For "testif HAVE_QRUPDATE", __feat{1}{1} would be HAVE_QRUPDATE.
>
> If you think this would be a useful thing to be able to check for
> generally, then I think we should have a separate function for this,
> and maybe make it work more reliably than just using findstr on the
> value returned by octave_config_info ("DEFS").
>
> I can see where some feature checks like this might be useful, but I
> still think it would be best to avoid having very many checks of this
> kind in the Octave sources if possible.
>
> | OK. I originally considered rebasing QR & CHOL classes on a common
> | templated ancestor, but eventually I realized there was really not
> | that much code to share, as most methods are relatively thin wrappers
> | for the Fortran ones.
> | Still I can write a .cc file containing the replacement templates and
> | use that even in the current code.
>
> OK.
>
> Thanks,
>
> jwe
>

I've committed a changeset with the replacement routines. Also, the
first attempt to use them will issue a warning.
I haven't done any testing of the replacements beyond running make check.

regards

--
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: improved QR & Cholesky updating

John W. Eaton
Administrator
On 22-Jan-2009, Jaroslav Hajek wrote:

| I've committed a changeset with the replacement routines. Also, the
| first attempt to use them will issue a warning.
| I haven't done any testing of the replacements beyond running make check.

Thanks.

jwe