Use of zero-to-node VS node-to-node formulation for Q and QDelta

[tlunet]

Hi, this is a question mostly addressed to @pancetta and @danielru : in algebraic representation of SDC, for instance in the fast-wave slow-wave paper [1], SDC is defined using QDelta and Q matrix in zero-to-node formulation, i.e the system that is solved for one collocation step on $M$ nodes is :

$$(I - Q \text{ or }Q_\Delta) \begin{pmatrix} u_1 \cr \vdots \cr u_M \end{pmatrix} = \begin{pmatrix} u_0 \cr \vdots \cr u_0 \end{pmatrix} $$

which represents an update for one node solution $u_{m+1}$ depending on all previously computed $u_{m}$ + $u_0$ $\Rightarrow$ "zero-to-node" formulation.

But on an other reference from Michael Minion [2], the update of $u_{m+1}$ depend only on the previous corrected solution $u_{m}$ (using Backward or Forward Euler sweep) + the evaluation of the ODE RHS, either on $u_{m+1}$ (implicit) or $u_{m}$ (explicit). Since the update formula depends explicitly on the previously computed node, this is more a "node-to-node" formulation.

pySDC is based on "zero-to-node" formulation, and most recent paper on SDC have been using the same formulation, which is become kind of a standard (even if the "node-to-node" formulation is just a an equivalent way to write the algorithm, and can also be written algebraically).

But from my point of view, there is two advantages of the node-to-node formulation

1. Efficiency : usually when sweeping on one node, for one linear problem and implicit formulation, you have to build a RHS term of a linear system that contains all terms from the previous nodes (at iteration $k+1$), if you are using a zero-to-node formulation. Using a node-to-node formulation would allow to add fewer terms to build the RHS, especially for the last nodes, hence reduce the number of flops for each sweep.
2. QDelta definition : this matrix is viewed as a low order sequential time integration between each node (for instance using Implicit or Explicit Euler steps), for which the zero-to-node formulation is not really natural (usually, we look at those method using a node-to-node formulation, since the update for one time step depends mostly on the previous one). Also, defining other QDelta from different time integration method (for instance, a multistep method within the node) would be much easier to do in node-to-node formulation.

My question is then : why zero-to-node formulation became kind of a standard when describing SDC in algebraic form ? I know that the Picard formulation of an ODE is by nature zero-to-node, but nothing prevents the use of its node-to-node form :

$$ u(t_{m+1}) = u(t_m) + \int_{t_m}^{t_{m+1}} f(u(\tau), \tau)d\tau, $$

and then build the whole collocation method and SDC correction from it ... Or is there some reasons I don't know that favor the use of the zero-to-node formulation ?

References

[1] Ruprecht, D., & Speck, R. (2016). Spectral deferred corrections with fast-wave slow-wave splitting. SIAM Journal on Scientific Computing, 38(4), A2535-A2557.

[2] Minion, M. L. (2003). Semi-implicit spectral deferred correction methods for ordinary differential equations. Communications in Mathematical Sciences, 1(3), 471-500.

[pancetta]

Hey @tlunet, you're right with pretty much all you said. One thing we figured out at some point is that the node-to-node formulation (or "S-fomulation") the algebraic formulation was not as easy to analyze as an iterative method as the zero-to-node formulation (or "Q-formulation"), at least for us.

In addition, I recall that when writing the first version of pySDC, the zero-to-node formulation was simpler to implement, esp. if there are explicit parts. I am well aware of the reduced efficiency, but at some point it indeed became a habit to resort to the zero-to-node formulation.

That said, I'm pretty sure that there is nothing preventing you from using the node-to-node formulation.

[pancetta]

Btw., in the Boris code, we actually rely on the node-to-node formulation, because there the right-hand-side in the zero-to-node formulation is really not straightforward, to us at least.

[danielru]

This is only if you do the substitution, I believe? In our second Boris-SDC paper where we do not use substitution, it is fairly straightforward to write down. But since the Boris code in pySDC does use substitution (and some of Ikrom's results suggest that this is beneficial), zero-to-node might indeed be hard to do.

[tlunet]

Oh, just find one main advantage of zero-to-node formulation : if you want to build a diagonal QDelta matrix, than you cannot do it in node-to-node formulation !

So probably any SDC code for practical application should be able to switch between node-to-node and zero-to-node formulation ...

[pancetta]

Oh, very good argument!!