## 2 Preliminaries: Main Tools and Requirements
### The MGRIT Algorithm  
We provide a brief overview of the MGRIT method introduced in [21]. Assume we are given the initial value problem  
\[u^{\prime}(t) =f(t,u(t)),\quad t\in(0,T),\] \[u(0) =u_{0},\]  
where \(f\) is a given function and \(u_{0}\) is the initial condition. Let \(0=t_{0}<t_{1}<\ldots<t_{N-1}<t_{N}=T\) be a uniform mesh given on the interval \([0,T]\) with an equidistant step size \(\Delta t\).  
In standard time-stepping approaches, the solution is approximated using a one-step method  
\[u_{0} =u_{0},\] \[u_{i+1} =\Phi_{i+1}(u_{i})+g_{i+1},\quad i=0,1,\ldots,N-1,\]  
where \(\Phi\) denotes the one-step update operator, which can be practically any Runge-Kutta method, and \(g\) represents the source or correction terms. Since each time point depends on the previous one, this yields a sequential algorithm in time.  
In contrast, the MGRIT algorithm iteratively computes an approximation to the solution over the entire time domain, starting from an initial guess. MGRIT is based on multigrid techniques and enables parallelization in the temporal domain. Assume that the right-hand side \(f\) is linear, and consider a coarser time grid \(0=T_{0}<T_{1}<\ldots<T_{\frac{N}{N-1}}<T_{\frac{N}{N}}=T\) with a step size \(\Delta T=m\Delta t\). On this coarse grid, we apply another one-step method, denoted by \(\Phi_{\Delta}\), which is computationally cheap and used to improve the current approximation. The two-grid method, which is equivalent to the parareal method [22], is outlined in Algorithm 1. The relaxation steps are illustrated in Figure 1.  
```
1: Relaxation by F-relaxation (or FCF-relaxation)
2: Restriction: \(r_{\Delta,i}=u_{mi}-(\Phi_{mi}(u_{mi-1})-g_{mi})\)
3: Solve the problem \(v_{\Delta,i}=\Phi_{\Delta}(v_{\Delta,i-1})+r_{\Delta,i}\) in the coarse grid
4: Prolongation: \(u_{im}=u_{im}+v_{\Delta,i}\)
5: Relaxation by F-relaxation
```  
**Algorithm 1** Two-grid method.  
The convergence rate of the two-grid method depends on how accurately the coarse-grid propagator \(\Phi_{\Delta}\) approximates the result of performing \(m\) successive fine-grid steps between two coarse time points. Selecting an optimal coarse-grid propagator remains an active area of research. In many practical settings, the same numerical method is employed on both the fine and coarse grids.  
A potential limitation of the two-grid approach is that the coarse grid may still be too fine, rendering Step 3 of Algorithm 1 computationally expensive. This issue can be addressed by recursively applying the same algorithm on increasingly coarser grids, following  
Figure 1: Illustration of F- and C-relaxation schemes.  
the classical multigrid paradigm. The resulting recursive structure gives rise to various cycle types, such as V-, W-, and F-cycles, as illustrated in Figure 2. Furthermore, the algorithm can be extended to nonlinear problems using the Full Approximation Scheme (FAS).  
The MGRIT algorithm achieves optimal complexity with a runtime of \(\mathcal{O}(N)\) and, unlike traditional time-stepping schemes, is massively parallelizable. In practice, convergence to a sufficiently accurate solution is often attained within a few iterations. The numerical results of strong scaling studies on a linear problem (heat equation) and a nonlinear problem (\(p\)-Laplace problem) are presented in [21; 23]. These results show that while the sequential one-step method outperforms MGRIT with a small number of processors, significant speedup is achieved when parallel resources are effectively utilized.  
The XBraid software package is an implementation of the MGRIT method [30]. It is written in MPI/C with interfaces for C++, Fortran 90, and Python, and is designed to be non-intrusive. This allows users to leverage their existing sequential time-stepping code, while XBraid manages the parallelization. Additionally, XBraid supports time refinement, enabling adaptive time-stepping strategies within the parallel-in-time framework. We used this implementation of the MGRIT method in the experiments presented in the next section.