Implementation details for high order IMEX methods by Kennedy and Carpenter

This question is a continuation of Fourth order IMEX Runge-Kutta method, concerning the implementation. Is seems to me that the first implicit stage value involves a direct evaluation, rather than solving some equation. That is, if $\frac{d U(t)}{dt} = F_{\textit{STIFF}}(t)+F_{\textit{NONSTIFF}}(t)$, and the stages are denoted by $k^{i}_{\textit{STIFF}}$ and $k^{i}_{\textit{NONSTIFF}}$, then $k^{1}_{\textit{STIFF}} = F_{\textit{STIFF}}$.

This seems to be in common for most schemes, as the Butcher tableau for the implicit part has only nonzero elements in the first column. However, this does not seem like an implicit treatment. What have I missed?

This seems to be in common for most schemes, as the Butcher tableau for the implicit part has only nonzero elements in the first column. However, this does not seem like an implicit treatment. What have I missed?

This is called an ESDIRK method, or an Explicit first step Singly-Diagonal Implicit Runge-Kutta method. The explicit first step is required to achieve the high order conditions for DAEs (called "stiffly-accurate"). Another order condition is that FSAL is required, so you'll notice that all of the schemes do that too, and since it's ESDIRK you can just flip that over to be the first stage and so actually there's no explicit evaluation required (depending on the quantities you are saving).

You need to be careful there though since the iterations will only be numerically stable for highly stiff equations if you relax the dt*f term instead of the input itself. This is something discussed in Shampine's TRBDF2 paper. Thus the Sundials implementation is a good resource, but if you've ever opened up Sundials you'll notice that something weird happens in the test equations (and the test equations require dropping the convergence coefficient quite a bit). My theory is that this is due to their iteration choice since the DifferentialEquations.jl versions don't have this issue. This means that, when you do find an equation where they work, they have higher runtimes than they should... For reference, here's the open source Julia implementation of the 3rd order KenCap in out-of-place form if you want to copy some things. In-place forms along with the other orders are also in that file.

Edit

As mentioned in another post, the FSAL property is only on the implicit part of the tableau. Thus when you use this as an ESDIRK method it is FSAL, and that's one of the stiffly-accurate order conditions. However, the update value is not directly from the implicit tableau when solving with IMEX, so the first step of the implicit part does need a function evaluation.

• So FSL stands for \emph{First Same As Last}, which does explain it all to some extent. But you still need to initiate the time--stepping procedure, where you can't rely on previous values. So the explicit evaluation of the stiff right hand side term sill occurs. Could you please explain by an example, for instance ARK4(3)6L[2]SA-ESDIRK from ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/20010075154.pdf To me it seems as if the first stage is still $k^{1}_{\textit{STIFF}} = F_{\textit{STIFF}}$. Cheers – Raibyo Feb 20 '18 at 15:25
• Yes, you do need an evaluation to get it started, and it's just f_implicit at the initial condition and initial time point. – Chris Rackauckas Feb 20 '18 at 16:07
• Thank you, I will look into FSAL. In my case $\texttt{f_implicit}$ is not known, so I will try another approach. I have $u_{t} = \alpha^{2}\Delta u_{t} + f(t)$, the idea is to treat $f$ explicitly and $\Delta u$ implicitly, and thereby solve for $u$ at the stages. However, this will not work with ESDIRK. – Raibyo Feb 20 '18 at 16:18
• I don't get the issue there. Do you not have the function defined in a way that you can evaluate it? If not, how are you doing the quasi-Newton iterations? – Chris Rackauckas Feb 20 '18 at 16:19
• \texttt{f_implicit} is not defined in a way such that it can be evaluated. In my specific I do not use quasi-Newton iterations, but a PDE instead. Strictly, it is not an IMEX method I use. However, what I propose works well in combination with an Explicit Implicit RK2 method. For the IMEX methods it comes down to avoid evaluating \texttt{f_implicit} explicitly. – Raibyo Feb 20 '18 at 16:35