5
$\begingroup$

I’m trying to find a Runge–Kutta integrator that only requires the absolute minimum of storage, i.e. it fulfills one of the following three, presumably equivalent criteria:

  • Each evaluation of the derivative should only depend on the previous stage.

  • It stores only store three vectors, namely the beginning of the step, an intermediate temporary copy, and the end of the step, which is incrementally updated each stage (the temporary copy can then be overwritten in each stage).

  • It has a “diagonal Butcher tableau”.

The classical fourth-order Runge–Kutta method (RK4) is an example of this, but I am struggling to find such methods for higher orders. Do they exist?

|cite|improve this question
$\endgroup$
  • $\begingroup$ I don't think I've come across any. The number of stages would grow quite fast in order to make it work so I am not sure it would be practical anyways. $\endgroup$ – Chris Rackauckas Jan 24 '18 at 17:24
  • $\begingroup$ Just being curious: For what application do you need this? $\endgroup$ – Wrzlprmft Jan 24 '18 at 21:12
  • 1
    $\begingroup$ To be clear: those three things are not equivalent; also, the Butcher tableau for RK4 is not "diagonal" by the usual meaning of that word. Nor is that requirement a necessary condition for the low-storage property. $\endgroup$ – David Ketcheson Jan 25 '18 at 7:39
  • $\begingroup$ I have an implementation of RK4 with three copies of each dynamical quantity, and due to memory constraints do not want to increase this number. I was just curious if I could get a higher-order scheme without adding storage. However, it makes sense that the number of required stages would grow to be not practical. (This is indeed out of curiosity rather than an explicit need. By extension, I would be interested in higher-order methods which only involve one extra "temporary" copy, i.e., to totals.) $\endgroup$ – zjw518 Jan 25 '18 at 20:00
10
$\begingroup$

This area has been fairly well researched, you may check e.g. Ketcheson's review of such methods:

https://doi.org/10.1016/j.jcp.2009.11.006

which does contain some low-storage Runge-Kutta methods for fifth and sixth orders.

|cite|improve this answer
$\endgroup$
7
$\begingroup$

Another good starting point is the excellent paper of Kennedy, Carpenter, & Lewis (KCL2000):

https://doi.org/10.1016/S0168-9274(99)00141-5

My own paper focuses more on the mechanics of low-storage implementation and what it implies for method construction, while KCL2000 is heavily focused on optimization and testing of methods. They give an extensive investigation of methods up to fifth order. Very little has been done regarding low-storage explicit RK methods of higher than fifth order (my own paper, linked in the other answer, is an exception).

I will add that there is a better way to implement RK4 in low storage than the obvious one, and every 4th-order RK4 method has a low-storage implementation (3 registers). These things are explained in detail in references provided in the introduction of my paper already linked by @reid.atcheson.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Are there any implementations in the wild suitable for benchmarking with? $\endgroup$ – Chris Rackauckas Jan 25 '18 at 11:28
  • $\begingroup$ Quite possibly, but none that I can think of offhand. $\endgroup$ – David Ketcheson Jan 26 '18 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.