Impact of spatial coarsening on Parareal convergence for the linear advection equation

Basic Information

• 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

Abstract

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.

Research Background and Motivation

Problem Background

1. 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.
2. 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.
3. 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.

Research Motivation

1. Difficulty in Theoretical Prediction: It is currently difficult to predict a priori whether a given Parareal configuration exhibits monotonic convergence or initial error growth.
2. Impact of Spatial Coarsening: Understanding the specific mechanisms by which reduced spatial resolution in the coarse propagator affects convergence is needed.
3. Convergence Assessment Tools: Reliable theoretical tools are needed to distinguish different convergence behavior patterns.

Core Contributions

1. 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).
2. Lower Bound Theorem: Provides theoretical lower bounds for the 2-norm of the Parareal error propagation matrix using spatial coarsening.
3. Pseudospectral Analysis: First applies pseudospectral theory to Parareal convergence analysis, demonstrating that the pseudospectral radius can reliably predict convergence behavior.
4. 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.

Detailed Methodology

Problem Formulation

Study the convergence of the Parareal method for linear initial value problems: $y'(t) = Ay(t), \quad y(0) = b, \quad t \in [0,T]$ where $A \in \mathbb{C}^{n \times n}$, $b \in \mathbb{C}^n$.

Core Theoretical Framework

Parareal as Linear Fixed-Point Iteration

For linear problems, Parareal can be written as a fixed-point iteration: $M_g y^{k+1} = (M_g - M_f)y^k + b$

where the error propagation matrix is: $E = M_g^{-1}(M_g - M_f) = I - M_g^{-1}M_f$

Spatial Coarsening Treatment

One application of the coarse method becomes: $G_{\Delta t}(y) = I\tilde{G}_{\Delta t}(Ry)$ where $R \in \mathbb{C}^{m \times n}$ is the restriction operator and $I \in \mathbb{C}^{n \times m}$ is the interpolation operator.

Error Propagation Matrix Structure

$E = \begin{pmatrix} 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

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.