patchGNU Octave - Patches: patch #8047, New function for odepkg

 
 

patch #8047: New function for odepkg

Submitted by:  Carlo de Falco <cdf>
Submitted on:  Mon 13 May 2013 07:33:34 AM UTC  
 
Category: NonePriority: 5 - Normal
Status: NonePrivacy: Public
Assigned to: Carlo de Falco <cdf>Open/Closed: Open

Add a New Comment (Rich MarkupRich Markup):
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

Thu 27 Jun 2013 03:23:39 PM UTC, comment #7:

Following the discussion we had at OctConf,
the approach we decided to take is to have one single bwe ode solver where the method used for nonlinear equation solving is left as an option.
c.

Carlo de Falco <cdf>
Project MemberIn charge of this item.
Wed 15 May 2013 10:48:57 AM UTC, comment #6:

Dear Carlo,

I had chosen the classical half-step approach because it is robust and easy to implement (I thought I used Richardson extrapolation? Then it should also be second order). Anyway, I guess that the difference is negligible and we could go for odebwenk here without any loss.

I propose odeset('nlssolver',@function) as an option for odebwe with fallback to a private newton scheme. Then we don't need a dependency on optim because it's the user's responsibility.

Checking for the package is also fine (I personall check for functions because I want to keep matlab compatibility).

Bye
Sebastian

Sebastian <sschoeps>
Tue 14 May 2013 04:13:55 PM UTC, comment #5:

Sebastian,

I like the idea of merging the current odebwe solver and odebwenk
but there is one more issue to be solved to do so.

odebwenk uses a 2nd order corrector to estimate local truncation error while odebwe uses a solution with half the time step as a reference.

probably we could set also this as an option, but I don't see an easy way to switch from one approach to the other.
How would propose to do that?

As for checking for existence on the inexact_newton function, we usually do not check for individual files but only for packages.

Carlo de Falco <cdf>
Project MemberIn charge of this item.
Tue 14 May 2013 12:27:45 PM UTC, comment #4:

On Tue, May 14, 2013 at 08:25:56AM +0200, c. wrote:

> <snip>
> Yes it is meant for problems with large, sparse jacobians
> <snip>
> indeed it is a zero-finder but many ptimization functions could made
> to optionally use it when dealing with large problems.


Principally yes, but this probably has some issues:

- It would be an algorithm without constraints (but this could be
o.k. due to its specialization).

- The user could not, as usual, specify a Hessian function of the
parameters directly, but would have to do it indirectly for
this algorithm by specifying a jacobian (for inexact_newton)
of the gradient function (of the outer algorithm).

- A user-specified (in which way whatever) Hessian would not
necessarily be positive definite. This can spoil the outer
algorithm which uses inexact_newton.

- A user-specified Hessian isn't even necessarily non-singular.
I'm not sure that inexact_newton would cope with that.

> <snip>
> so you suggest adding inexact_newton both in odepkg and optim? I
> think it could be done if we make it private in odepkg to avoid
> conflicts ...


Yes, something like that. I don't suggest it, but it would be a way if you value independence. Which Sebastian seems to do. I think this way would also be compatible with his suggestion to make inexact_newton rather a configurable sub-algorithm of an existing solver.

Anyway I think it could be good if this function were also in 'optim'.

Olaf

Olaf Till <i7tiol>
Tue 14 May 2013 12:23:43 PM UTC, comment #3:

Re-posted for Carlo de Falco <kingcrimson@tiscali.it>
(Actually the order of this and the previous post was reversed, sorry.):
---------------------------------------------------------------

On 13 May 2013, at 22:10, Olaf Till <INVALID.NOREPLY@gnu.org> wrote:

> Follow-up Comment #1, patch #8047 (project octave):
>
> As I understand, the inexact Newton method, as well as the ODE solver which
> uses it, is meant for large scale problems --- is that right?


Yes it is meant for problems with large, sparse jacobians

> If specially suitable for large scale problems, I think 'inexact_newton' could
> be a valuable alternative to 'fsolve', and so would fit well into the 'optim'
> package (I believe it would be the first zero-finder there, except a
> vectorized clone of 'fzero').


indeed it is a zero-finder but many ptimization functions could made to optionally
use it when dealing with large problems. I'd like the function to be given more testing
before such changes are done, though.

> The dependency on other packages can sometimes be a problem, though. 'optim'
> sometimes makes problems on some systems due to its use of LAPACK, and it in
> turn depends on further packages, partially due to some older code. Maybe
> eventually some reorganization will happen; until that, duplicating the code
> of 'inexact_newton' in the 'odepkg' package could be an (ugly) solution for
> being independent …


so you suggest adding inexact_newton both in odepkg and optim?
I think it could be done if we make it private in odepkg to avoid conflicts ...

> Or 'inexact_newton' might actually go into Octave core, if it is really good
> for large scale problems.


I don't think it fits in Octave core, its scope does not seem general enough to me
and there is not an equivalent function in Matlab

> But that is not mine to decide. Its interface would
> probably have to be changed for that in favor of 'optimset' (and maybe this
> would even be better anyway).


that is a good idea.

> Olaf

c.

Olaf Till <i7tiol>
Tue 14 May 2013 12:21:34 PM UTC, comment #2:

Re-posted for Sebastian Schöps <schoeps@gsc.tu-darmstadt.de>:
-------------------------------------------------------------

The backward Euler that I have written (odebwe.m) uses a private Newton scheme to avoid dependencies. I would encourage to merge the two integrators.

Instead there should be a switch in odeset to choose the nonlinear solver (fixed point, Newton, simplified Newton, Krylov) as suggested by Olaf. I would prefer
+to keep the classical Newton build-in and the others could be made optional with something like "if !exist(...,'file') warning('Install Optim')".

Best regards,
Sebastian

Am 14.05.2013 um 08:25 schrieb "c." <kingcrimson@tiscali.it>:

>
> On 13 May 2013, at 22:10, Olaf Till <INVALID.NOREPLY@gnu.org> wrote:
>
>> Follow-up Comment #1, patch #8047 (project octave):
>>
>> As I understand, the inexact Newton method, as well as the ODE solver which
>> uses it, is meant for large scale problems --- is that right?
>
> Yes it is meant for problems with large, sparse jacobians
>
>> If specially suitable for large scale problems, I think 'inexact_newton' could
>> be a valuable alternative to 'fsolve', and so would fit well into the 'optim'
>> package (I believe it would be the first zero-finder there, except a
>> vectorized clone of 'fzero').
>
> indeed it is a zero-finder but many ptimization functions could made to optionally
> use it when dealing with large problems. I'd like the function to be given more testing
> before such changes are done, though.
>
>> The dependency on other packages can sometimes be a problem, though. 'optim'
>> sometimes makes problems on some systems due to its use of LAPACK, and it in
>> turn depends on further packages, partially due to some older code. Maybe
>> eventually some reorganization will happen; until that, duplicating the code
>> of 'inexact_newton' in the 'odepkg' package could be an (ugly) solution for
>> being independent …
>
> so you suggest adding inexact_newton both in odepkg and optim?
> I think it could be done if we make it private in odepkg to avoid conflicts ...
>
>> Or 'inexact_newton' might actually go into Octave core, if it is really good
>> for large scale problems.
>
> I don't think it fits in Octave core, its scope does not seem general enough to me
> and there is not an equivalent function in Matlab
>
>> But that is not mine to decide. Its interface would
>> probably have to be changed for that in favor of 'optimset' (and maybe this
>> would even be better anyway).
>
> that is a good idea.
>
>> Olaf
> c.

Olaf Till <i7tiol>
Mon 13 May 2013 08:10:57 PM UTC, comment #1:

As I understand, the inexact Newton method, as well as the ODE solver which uses it, is meant for large scale problems --- is that right?

If specially suitable for large scale problems, I think 'inexact_newton' could be a valuable alternative to 'fsolve', and so would fit well into the 'optim' package (I believe it would be the first zero-finder there, except a vectorized clone of 'fzero').

The dependency on other packages can sometimes be a problem, though. 'optim' sometimes makes problems on some systems due to its use of LAPACK, and it in turn depends on further packages, partially due to some older code. Maybe eventually some reorganization will happen; until that, duplicating the code of 'inexact_newton' in the 'odepkg' package could be an (ugly) solution for being independent ...

Or 'inexact_newton' might actually go into Octave core, if it is really good for large scale problems. But that is not mine to decide. Its interface would probably have to be changed for that in favor of 'optimset' (and maybe this would even be better anyway).

Olaf

Olaf Till <i7tiol>
Mon 13 May 2013 07:33:34 AM UTC, original submission:

Dear Sebastian, Olaf,

Please find attached a new submission I'd like to be included
in ODEPKG it implements an adaptive timestep Backward-Euler solver that uses a Newton-Krylov solver for non-linear system solution, implemented by Simone Panza and Fabio Cisaria.

The main reason for posting this contribution here rather than commiting to the subversion repository directly is that I need help deciding what should be done with the "inexact_newton" function.

Personally I believe the inexact_newton function has use beyond the scope of ODEPKG so maybe it should rather go into the optim package.

This though would impose a dependence of odepkg on optim, which is something that the previous maintainer of odepkg has always tried to avoid (odepkg currently has no additional dependencies). Therefore I'd like you to comment on where this function fits better before committing.

Thanks,
Carlo

Carlo de Falco <cdf>
Project MemberIn charge of this item.

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

Attached Files
file #28073:  odebwenk.m added by cdf (7kB - application/octet-stream)
file #28074:  inexact_newton.m added by cdf (6kB - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by sschoeps (Posted a comment)
  • -unavailable- added by i7tiol (Posted a comment)
  • -unavailable- added by cdf (Submitted the item)
  • -unavailable- added by cdf
  • -unavailable- added by cdf
  • -unavailable- added by cdf
  • -unavailable- added by cdf
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 6 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon 13 May 2013 07:33:34 AM UTCcdfAttached File-=>Added odebwenk.m, #28073
      Attached File-=>Added inexact_newton.m, #28074
      Carbon-Copy-=>Added -unavailable-
      Carbon-Copy-=>Added -unavailable-
      Carbon-Copy-=>Added -unavailable-
      Carbon-Copy-=>Added -unavailable-

    Back to the top


    Powered by Savane 3.1-cleanup