Spectral Deferred Correction & Co

📯 This wiki intends to accumulate theoretical content and literature references on SDC and related time integration methods, with a specific focus on the algorithms implemented in pySDC. Its goal is to be an evolving source of knowledge, that could be used by people starting to learn about SDC, or eventually specialists in this field. Any contribution to improve it is very welcome !

Spectral Deferred Correction (SDC) methods are a class of time-stepping algorithm allowing to approximate the solution of initial value problem of the form :

$$ \frac{du}{dt} = f(u,t),\quad t \in [0, T],\quad u(0) = u_0 $$

Those can Ordinary Differential Equations (ODEs) or systems of ODEs resulting from the partial discretization of Partial Differential Equations (PDEs). SDC was originally introduced in 2000 [1], based on the previously known Deferred Correction method, and allows to easily build time integration schemes with piloted order of accuracy (from low to high). It has received a particular attention since then, e.g for the development of Implicit-Explicit (IMEX) time integration scheme [2] or parallel-in-time methods [3]. Many variants have been developed since, and this Wiki intends to provide a extended state-of-the art overview of SDC methods and their implementations.

Table of content

🛠️ In construction ...

To get started

1. Picard Formulation and Collocation methods
2. Deferred Correction method and Gauss quadrature
3. SDC sweep using low-order approximation
4. Time-stepping and prolongation

Advanced concepts

1. Error analysis and accuracy order
2. Algebraic representation
3. Node-to-node and zero-to-node formulation
4. High order SDC sweep
5. Numerical linear stability

SDC variants

1. IMEX-SDC
2. Second Order Boris SDC
3. Adaptive and Fault-tolerant SDC
4. SDC for first order system of ODE's with mass matrix

Parallel-in-time integration

1. Combining Parareal and SDC
2. Multilevel-SDC
3. Parallel Full Approximation Scheme in Space and Time (PFASST)
4. Revisionist Integral Deferred Correction (RIDC)
5. Block Gauss-Seidel SDC

[1] Dutt, A., Greengard, L., & Rokhlin, V. (2000). Spectral deferred correction methods for ordinary differential equations. BIT Numerical Mathematics, 40(2), 241-266.

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

[3] Emmett, M., & Minion, M. (2012). Toward an efficient parallel in time method for partial differential equations. Communications in Applied Mathematics and Computational Science, 7(1), 105-132.