1
$\begingroup$

I'm looking for a 3rd order Runge-Kutta scheme of order 3 (or higher) with low-storage, which means that not all intermediate results must be stored concurrently. I found an old paper which presents exactly this. The paper is A Kutta Third-Order Procedure for Solving Differential Equations Requiring Minimum Storage, by S.Conte and R.Reeves and appeared back in 1956 and is only 4 pages long.

In section 3 of that article the algorithm is depicted in a way that makes clear that just two arrays are sufficient to store the initial value, the intermediate values and the result (of course these arrays are overwritten multiple times). The algorithm has 6 steps:

  1. Have initial solution in array B : $B \leftarrow y$
  2. Compute k0 : $A \leftarrow h \cdot f(t; B)$
  3. Compute y1 : $A \leftarrow B + a \cdot A$
  4. Compute k1 : $B \leftarrow h \cdot f(t+a; A)$
  5. Compute y2 : $A \leftarrow A + r \cdot B$
  6. Compute y3 : $B \leftarrow A + (b-r)*B + c \cdot k_2$

Now, step 6 cannot be performed before computing $k_2$. To do so with just two arrays one could update the array A by doing $A = A + c \cdot h \cdot f(t+n; A)$, which cannot be computed in-place if f needs to access values in the array other than the one it is computing (e.g. in case it needs to compute some finite-difference derivative of the array) [unless some kind of programmable cache is present in the computer which for sure did not exist back then].

My question is then how do the author plan to perform the step 6 of the integration with just two arrays. Am I missing something obvious?

P.S.: somebody should create the tag "Runge-Kutta" or similar. There are many questions related to this kind of numerical integration, but I cannot create this tag because I don't have enough reputation.

$\endgroup$
1
$\begingroup$

Probably the problem can be solved differently than I initially thought. We can split step 6 into two sub-steps:

6a. Update B : $B \leftarrow (b-r) \cdot B+c \cdot h \cdot f(t+n; A) \quad = \quad (b-r) \cdot k_1 + c \cdot k_2$

6b. Update B with final solution : $B \leftarrow A + B \quad = \quad y + a \cdot k_0 + r \cdot k_1 + (b-r) \cdot k_1 + c \cdot k_2 ~ = ~ y +a \cdot k_0 + b \cdot k_1 + c \cdot k_2$

$\endgroup$

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.