The Parareal parallel-in-time integration method often performs poorly when applied to hyperbolic partial differential equations. This effect is even more pronounced when the coarse propagator uses a reduced spatial resolution. However, some combinations of spatial discretization and numerical time stepping nevertheless allow for Parareal to converge with monotonically decreasing errors. This raises the question how these configurations can be distinguished theoretically from those where the error initially increases, sometimes over many orders of magnitude. For linear problems, we prove a theorem that implies that the 2-norm of the Parareal iteration matrix is not a suitable tool to predict convergence for hyperbolic problems when spatial coarsening is used. We then show numerical results that suggest that the pseudo-spectral radius can reliably indicate if a given configuration of Parareal will show transient growth or monotonic convergence. For the studied examples, it also provides a good quantitative estimate of the convergence rate in the first few Parareal iterations.
- Paper ID: 2111.10228
- Title: Impact of spatial coarsening on Parareal convergence for the linear advection equation
- Authors: Judith Angel, Sebastian Götschel, Daniel Ruprecht (Hamburg University of Technology)
- Classification: math.NA cs.CE cs.NA
- Publication Date: November 2021 (arXiv preprint, latest revision October 2025)
- Paper Link: https://arxiv.org/abs/2111.10228
The Parareal time-parallel integration method typically exhibits poor performance when applied to hyperbolic partial differential equations, with this effect becoming more pronounced when the coarse propagator uses reduced spatial resolution. However, certain combinations of spatial discretization and numerical time-stepping still allow Parareal to converge with monotonically decreasing errors. This paper investigates how to theoretically distinguish these configurations from those exhibiting initial error growth (sometimes exceeding many orders of magnitude). For linear problems, the authors prove a theorem demonstrating that the 2-norm of the Parareal iteration matrix is not an appropriate tool for predicting convergence of hyperbolic problems using spatial coarsening. Numerical results indicate that the pseudospectral radius can reliably indicate whether a given Parareal configuration exhibits transient growth or monotonic convergence, and provides good quantitative estimates of convergence rates for the first several Parareal iterations.
- Parallel Computing Bottleneck: With the rapid increase in the number of processing units in modern high-performance computers, numerical algorithms must provide as many levels of parallelization as possible. Time-stepping has become a serial bottleneck in simulations involving the approximate solution of time-dependent differential equations.
- Time-Parallel Methods: Time-parallel integration methods such as Parareal, PFASST, and MGRIT have been proposed as alternatives to overcome the scalability limitations of pure spatial parallelization.
- Challenges for Hyperbolic Problems: It is well-known that Parareal convergence for hyperbolic problems is typically poor, particularly when combined with spatial coarsening, though this is not always the case.
- Difficulty in Theoretical Prediction: It is currently difficult to predict a priori whether a given Parareal configuration exhibits monotonic convergence or initial error growth.
- Impact of Spatial Coarsening: Understanding the specific mechanisms by which reduced spatial resolution in the coarse propagator affects convergence is needed.
- Convergence Assessment Tools: Reliable theoretical tools are needed to distinguish different convergence behavior patterns.
- Theoretical Contribution: Proves that for linear initial value problems with normal system matrices, the 2-norm of the Parareal iteration matrix cannot be used to assess convergence (Theorem 1).
- Lower Bound Theorem: Provides theoretical lower bounds for the 2-norm of the Parareal error propagation matrix using spatial coarsening.
- Pseudospectral Analysis: First applies pseudospectral theory to Parareal convergence analysis, demonstrating that the pseudospectral radius can reliably predict convergence behavior.
- Numerical Verification: Validates the effectiveness of the pseudospectral radius as a convergence prediction tool through numerical experiments on the linear advection equation with four different configurations.
Study the convergence of the Parareal method for linear initial value problems:
y′(t)=Ay(t),y(0)=b,t∈[0,T]
where A∈Cn×n, b∈Cn.
For linear problems, Parareal can be written as a fixed-point iteration:
Mgyk+1=(Mg−Mf)yk+b
where the error propagation matrix is:
E=Mg−1(Mg−Mf)=I−Mg−1Mf
One application of the coarse method becomes:
GΔt(y)=IG~Δt(Ry)
where R∈Cm×n is the restriction operator and I∈Cn×m is the interpolation operator.
0 & & & \\
B_0 & 0 & & \\
B_1 & B_0 & 0 & \\
\vdots & \ddots & \ddots & \ddots \\
B_{P-1} & \cdots & B_1 & B_0 & 0
\end{pmatrix}$$
where $B_k = G^k(F-G)$.
### Technical Innovations
#### 1. Theoretical Lower Bound (Theorem 1)
For normal matrices $A$, the 2-norm of the Parareal error propagation matrix satisfies:
$$\|E\|_2 \geq \sqrt{\sum_{j=m+1}^n |R_f(\lambda_j \delta t)^{N_f}|^2} \geq |R_f(\lambda_{m+1}\delta t)|^{N_f}$$
#### 2. Numerical Diffusion Classification
- **Physical Diffusion**: Inherent properties of the problem (e.g., heat equation)
- **Spatial Numerical Diffusion**: Artificial diffusion introduced by spatial discretization
- **Temporal Numerical Diffusion**: Diffusion introduced by the time-stepping scheme
#### 3. Pseudospectral Analysis Method
Uses the pseudospectral radius $\rho_\varepsilon(E)$ to predict convergence behavior:
- If the pseudospectrum is near the unit circle, monotonic convergence is expected
- If the pseudospectrum has significant protrusions, transient growth is expected
## Experimental Setup
### Test Problem
Linear advection equation: $u_t + Uu_x = 0$, where $U = 1.0$, periodic boundary conditions, $x \in [0,1]$, $t \in [0,1]$.
### Four Configuration Comparison
| Configuration | Spatial Discretization | Propagator | Numerical Diffusion | Spatial Resolution (Fine/Coarse) |
|---|---|---|---|---|
| A | Upwind FD | Implicit Euler | Strong | 32/24 |
| B | Central FD | Trapezoidal | None | 32/24 |
| C | Spectral | RK443 | Weak | 32/24 |
| D | Spectral | RK443 | Weak | 32/30 |
### Evaluation Metrics
- Error propagation matrix norm $\|E\|_2$
- Pseudospectral radius $\rho_\varepsilon(E)$ ($\varepsilon = 0.1$)
- Iteration error $\|E^k\|_2$
- Final error magnitude
## Experimental Results
### Main Results
#### Convergence Behavior Comparison
- **Configuration A**: Fast monotonic convergence ($\|E\|_2 = 1.34$, final error $1.1 \times 10^{-3}$)
- **Configuration B**: Significant transient growth ($\|E\|_2 = 5.25$, final error $2.2 \times 10^1$)
- **Configuration C**: Significant transient growth ($\|E\|_2 = 7.74$, final error $3.2 \times 10^1$)
- **Configuration D**: Slow monotonic convergence ($\|E\|_2 = 1.29$, final error $3.0 \times 10^{-1}$)
#### Key Findings
1. **2-Norm Failure**: All configurations have $\|E\|_2 > 1$, unable to distinguish convergence behavior.
2. **Accurate Pseudospectral Prediction**: The pseudospectral radius accurately predicts monotonic convergence (A, D) and transient growth (B, C).
3. **Quantitative Estimation**: The pseudospectral radius $\rho_\varepsilon(E)^k$ provides good quantitative estimates of convergence rates for the first several iterations.
### Pseudospectral Analysis Results
- **Monotonic Convergence Configurations** (A, D): Pseudospectrum approximately circular, close to unit circle
- **Transient Growth Configurations** (B, C): Pseudospectrum severely distorted with large protrusions outside the unit circle
### Numerical Diffusion Impact
Experiments validate theoretical predictions:
- Strong diffusion (Configuration A): Fast convergence but poor numerical solution quality
- No diffusion (Configuration B): Severe phase errors and oscillations
- Weak diffusion (Configuration D): Slow but stable convergence
## Related Work
### Time-Parallel Methods
1. **Parareal Algorithm**: Classical method proposed by Lions, Maday, Turinici (2001)
2. **Other Methods**: PFASST, MGRIT, ParaDiag, RIDC, ParaExp, PSDC, etc.
3. **Theoretical Analysis**: Convergence analysis by Gander and Vandewalle; eigenvalue-based linear convergence analysis by Gander
### Challenges for Hyperbolic Problems
1. **Convergence Issues**: Parareal convergence for hyperbolic problems is typically poor
2. **Spatial Coarsening**: Further deteriorates convergence
3. **Optimization Strategies**: Optimized coarse propagator methods by De Sterck et al.
### Pseudospectral Theory
1. **Foundational Theory**: Monograph by Trefethen and Embree
2. **Application Domains**: Primarily used for analyzing non-normal matrices
3. **Novel Application**: First application to Parareal analysis in this paper
## Conclusions and Discussion
### Main Conclusions
1. **Theoretical Contribution**: Proves that the 2-norm is unsuitable for predicting Parareal convergence for hyperbolic problems with spatial coarsening.
2. **Practical Tool**: The pseudospectral radius can reliably predict convergence behavior and provide quantitative estimates.
3. **Role of Diffusion**: Numerical diffusion plays a critical role in Parareal convergence.
### Limitations
1. **Normal Matrix Restriction**: Theoretical results apply only to normal matrices (e.g., circulant matrices with periodic boundary conditions).
2. **Linear Problems**: Analysis is limited to linear initial value problems.
3. **Parameter Selection**: The choice of pseudospectral parameter $\varepsilon = 0.1$ lacks theoretical guidance.
### Future Directions
1. **Non-Normal Systems**: Extension to analysis of non-normal matrix systems.
2. **Optimized Operators**: Analysis of pseudospectral properties of optimized coarse propagators.
3. **Nonlinear Problems**: Exploration of pseudospectral methods for nonlinear problems.
## In-Depth Evaluation
### Strengths
1. **Theoretical Rigor**: Provides rigorous mathematical proofs and theoretical lower bounds.
2. **Innovative Tool**: First introduction of pseudospectral theory to Parareal analysis.
3. **Practical Value**: Provides actionable convergence prediction tools for practical applications.
4. **Comprehensive Verification**: Thoroughly validates theory through numerical experiments with multiple configurations.
### Weaknesses
1. **Limited Scope**: Theoretical results apply only to normal matrices, restricting applicability.
2. **Parameter Tuning**: Lack of systematic guidance for pseudospectral parameter selection.
3. **Computational Cost**: Computational complexity of pseudospectral calculations not discussed in detail.
### Impact
1. **Academic Value**: Provides new tools for theoretical analysis of time-parallel methods.
2. **Practical Significance**: Assists in selecting appropriate Parareal configurations for practical applications.
3. **Methodological Contribution**: Pseudospectral analysis methods may be applicable to other parallel algorithms.
### Applicable Scenarios
1. **Hyperbolic PDEs**: Particularly suitable for wave equations, advection equations, etc.
2. **Time-Parallel Requirements**: Large-scale scientific computing requiring time parallelization.
3. **Algorithm Design**: Guides design of new time-parallel algorithms.
## References
1. Lions, J.L., Maday, Y., Turinici, G.: A "parareal" in time discretization of PDE's (2001)
2. Gander, M.J., Vandewalle, S.: Analysis of the Parareal Time-Parallel Time-Integration Method (2007)
3. Trefethen, L.N., Embree, M.: Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators (2005)
4. De Sterck, H., et al.: Optimizing multigrid reduction-in-time and parareal coarse-grid operators for linear advection (2021)
---
**Summary**: By introducing pseudospectral theory, this paper provides new theoretical tools for analyzing Parareal convergence for hyperbolic problems. Despite certain limitations in scope, its theoretical contributions and practical value make it an important work in the field of time-parallel computing.