Support for implicit methods

[milancurcic]

FOODiE currently supports only explicit integration methods, i.e. methods that compute the solution at a future time based on the state at present and/or past times. Implicit methods require a guess of the state at a future time to obtain a more accurate solution. They are useful for some families of problems and in some cases may allow unconditionally stable integration with arbitrarily large time steps, at the expense of accuracy.

I believe that it is essential for FOODiE to include these methods, such as 1st order backward Euler, 2nd order trapezoidal, Adams-Moulton family of methods, Adams-Bashforth-Moulton etc.

Implicit solvers require evaluating the residual function R at time step n+1. This is usually done by a combination of initial guess and iterative procedure like Newton-Raphson iteration or similar. FOODiE should provide such methods for obtaining R at time step n+1. Once they are in place, implementation of the above-mentioned implicit methods should be trivial.

This issue aims to spark discussion on:

• How to implement evaluation of R(n+1) in FOODiE?
• What implicit methods do we want?
• Any other implementation / API suggestions.

[szaghi]

@milancurcic

You are completely right!

My answer is yes, we want implicit methods! All the ones you cited and many others: my boss @andreadimascio is thinking to a new adaptive scheme nlenfing continuosly from explicit to implicit mode...

I have only delayed to face with the problem on how compute the guess at new time step. In my workflow I typically use an iterative LU smoothing.

However, I think that the time is mature to face with the problem because the current API works well for explicit schemes.

I suggest to start with the simplest bacward Euler scheme. If tomorrow I will reduce my record of 5-seconds-to-lunch I will try a first approach :-)

Thank you Milan for focusing the pronlem

[szaghi]

@milancurcic

Unfortunately yesterday was a busy day, thus I cannot work on FOODiE for more than fews minutes.

Nevertheless, I have realized that we can start to play with implicit schemes very easily: implementing, for example, a class of Adams-Moulton solvers we will have the possibility to implement also a class of Adams-Bashforth-Moulton predictor-corrector that does not need iterators like Newton-Rapson or LU-substitution, thus it does not need any API changes. Do you agree? Today should be a more lucky day I hope: Adams-Moulton should come today.

See you later.

[szaghi]

@milancurcic

Implicit Adams-Moulton and predictor-corrector Adams-Bashforth-Moulton are within us!

The ABM is implemented very trivially by means of AB and AM: in particular it should be not so efficient (some computations can be avoided): however, it is just for testing the idea. It works very well: the observed order of accuracy with the Oscillation test is in agreement with the expectations and the global error is better than the explicit AB, namely one order lower!. The manuscript has some improvements on that.

Note that the AM cannot be used alone: I have not implemented a class of iterators. It is implemented like a fixed point algorithm: no iteration is done. As a consequence, it works well only when the guess is good, as it happens for the predictor-corrector ABD where the guess is provided by AB (of the same order, thus using one more step than AM counterpart).

I think that this proves that implicit solvers can be implemented into FOODiE with minor API changes.

Later, the predictor-corrector ABM can be made more efficient, but for the moment I am quite well with this implementation.

See you Monday.

[milancurcic]

@szaghi Amazing, thank you! :+1:

You work at a very fast pace, and it's sometimes difficult for me to catch up. Great job! I will go over all your updates over the weekend. :)

[szaghi]

Indeed today I spent about 2 hours on FOODiE... do not tell to my manager :-)

See you soon.

[zbeekman]

I plan on trying to look at this sometime in the next two weeks; that is generalizing FOODIE for implicit integration. I think it shouldn't be too hard to find an API... but first I need to catch up on what's been done.

[szaghi]

@zbeekman I agree, it should not be so difficult. Presently, the AM implicit family rely on a very trivial fixed point iteration that could perform very bad. I was thinking to add the imposition of provide a jacobian function into the ADT for adding a Newton's iteration and or impose a LU function... I cannot pre-figure how complex this is in practice.

[zbeekman]

yes, I think we need to find a way to keep it generic enough that the concrete implementation can specify and handle all the details of solving the implicit system

On Tue, Nov 17, 2015 at 4:01 PM Stefano Zaghi notifications@github.com wrote:

@zbeekman https://github.com/zbeekman I agree, it should not be so difficult. Presently, the AM implicit family rely on a very trivial fixed point iteration that could perform very bad. I was thinking to add the imposition of provide a jacobian function into the ADT for adding a Newton's iteration and or impose a LU function... I cannot pre-figure how complex this is in practice.

— Reply to this email directly or view it on GitHub https://github.com/Fortran-FOSS-Programmers/FOODIE/issues/21#issuecomment-157506129 .