Implement Multistep Methods for Comparison

[brownbaerchen]

We have diagonally implicit and explicit Runge-Kutta methods implemented for comparison between SDC and other algorithms.
If anyone ever feels bored, I think it would be nice to implement multistep methods as well.

I believe this can be more or less easily done by writing a new sweeper which replaces the SDC functionality with functions that are called at the appropriate time, but which instead do a different thing from what their name is.
For instance, the sweeper is based on a collocation problem, but multistep methods don't do collocation. They do something that looks quite similar, though. Instead of generating solutions at intermediate collocation nodes and updating all of them from each other, multistep methods update the solution at the current step from solutions at previous time points.

So, to generate a multistep method interface, we need to do:

• predict: Fill u and f in the levels with the values from previous time steps
• update_nodes: Compute the solution to the current step from the previous solutions, no loop over "nodes"
• compute_end_point: Return the solution at the last "node"
• compute_residual: We don't need to compute the residual at all, so do nothing.

Then, we would need to write some actual methods that only need to implement the update_nodes function to compute the solution to the current step.
And, we would need to profile this to make sure it is not doing any unnecessary work!

Again, this is not desperately needed! But I think it would be nice to have something in the interface of pySDC that does other methods in the language of SDC. If you feel like implementing this, please go ahead!

Please remember to test your methods. Ideally, you would test that they

• have the expected order of accuracy,
• are as stable as expected,
• and perform exactly as many right hand side evaluations as needed.

But feel free to deviate from this.

[lisawim]

That's a good idea! For DAEs, BDF methods are very familiar for solving them.

I want to add an important thing:
For implementing multistep methods, one also have to think about the start. For example, the k-step BDF Method needs k-1 initial values to start. Mostly, these initial values are not known, only the one at t0. So, in this case, the other k-2 values can be computed via other methods. When this is done, the computation is not started at time t0 anymore, but instead from time t_{k-1}. This is true for all multistep methods.
Thus, it makes sense to implement this in the controller class as well.

I was already starting with implementing BDF for DAEs.

[tlunet]

Are you thinking of multistep through the nodes or through the time-steps ? Because in both case, I see some issue there ...

[brownbaerchen]

I believe you can also do the startup period in the predict orupdate_nodes functions. I would avoid involving the controller at all cost ;)

I haven't thought this through to the end, so maybe there are some issues I didn't consider. But I don't want any nodes, I want to use the infrastructure with the nodes to put solutions and right hand side evaluations from previous steps in the nodes in predict to make them available in the update_nodes function, which uses these to compute the solution to the current step. I haven't really done multi step methods, so maybe I am missing something completely obvious here... Maybe I just need to try and implement a simple multi step method... I think that's the best way to learn