Source-linked AI summary
Analysis of a New Space-Time Parallel Multigrid Algorithm for Parabolic Problems
Martin J. Gander, Martin Neumüller
TL;DR
The paper addresses the sequential solution of time-dependent linear systems by developing a space-time parallel multigrid method for parabolic equations. It combines finite elements in space, discontinuous Galerkin discretization in time, and block-based smoothing, then analyzes convergence and evaluates parallel performance. The method converges under time semi-coarsening and can use full space-time coarsening when the discretization parameter is sufficiently large, while experiments report excellent strong and weak scaling.
Problem
Sequential forward substitution over time limits parallel solution of the global linear system, motivating a space-time method that exploits parallelism in both space and time.
Method
The paper develops a space-time multigrid algorithm for the heat equation using finite elements in space, discontinuous Galerkin discretization in time, and a block-diagonal smoother analyzed with local Fourier modes.
Results
The two-grid cycle converges with time semi-coarsening and permits full space-time coarsening when the discretization parameter μ is sufficiently large; experiments show excellent strong and weak scaling.
Takeaways & Limitations
The algorithm provides a space-time parallel solver for the heat equation and is also applicable to general parabolic problems, including time-dependent Stokes equations.
Takeaways & Limitations
The detailed Fourier analysis assumes a one-dimensional uniform spatial domain, and Fourier mode analysis is not rigorous for simulations without periodic boundary conditions.
Abstract
from arXiv · showhide
We present and analyze a new space-time parallel multigrid method for parabolic equations. The method is based on arbitrarily high order discontinuous Galerkin discretizations in time, and a finite element discretization in space. The key ingredient of the new algorithm is a block Jacobi smoother. We present a detailed convergence analysis when the algorithm is applied to the heat equation, and determine asymptotically optimal smoothing parameters, a precise criterion for semi-coarsening in time or full coarsening, and give an asymptotic two grid contraction factor estimate. We then explain how to implement the new multigrid algorithm in parallel, and show with numerical experiments its excellent strong and weak scalability properties.
1. Introduction.
The paper formulates a space-time discretization for the heat equation using finite elements in space and discontinuous Galerkin polynomials in time. This produces a block triangular system whose conventional solution is sequential, motivating a parallel multigrid method.
- The model problem is the heat equation on a bounded spatial domain with homogeneous Dirichlet boundary conditions.
- The time interval is partitioned into subintervals, with τ denoting the uniform time-step size.
- Finite elements in space and discontinuous Galerkin polynomials of order p_t in time produce a large space-time linear system.
- Each time step couples spatial mass and stiffness matrices through the block system [K_τ ⊗ M_h + M_τ ⊗ K_h]u^{n+1}.
- Forward substitution solves the block triangular system sequentially, whereas the proposed method solves the global system with a parallel space-time multigrid scheme.
2. Multigrid method.
The multigrid method builds a hierarchy of space-time meshes and uses block-Jacobi-style smoothing based on time-step blocks. Its convergence is analyzed with local Fourier modes, while implementation uses standard transfer operators and multigrid cycles.
- Multigrid hierarchy: The method constructs a hierarchical sequence of space-time meshes and system matrices, with the finest level representing the original system.
- Smoothing: The smoother approximates the inverse of a block diagonal matrix whose blocks correspond to individual time steps.
- Smoothing: Each block inverse can be approximated by one spatial multigrid V-cycle applied independently at each time step.
- Transfer operators: Standard interpolation transfers corrections from coarse to fine space-time grids, and restriction is chosen as the adjoint of prolongation.
- Fourier analysis: The analysis uses local Fourier mode analysis to study smoothing and two-grid convergence across low and high space-time frequencies.
- Analysis setting: For the one-dimensional analysis, the spatial domain is restricted to Ω = (0, 1) with uniform elements, while higher-dimensional analysis uses the same tools more technically.
3. Local Fourier mode analysis.
The local Fourier analysis characterizes block-Jacobi smoothing across space-time frequencies and distinguishes when semi-coarsening or full space-time coarsening provides effective damping. The resulting two-grid analysis shows convergence agreement between theoretical and numerical factors, with full coarsening requiring sufficiently large discretization parameters.
- Fourier-symbol framework: The analysis represents block-Jacobi smoothing through Fourier modes indexed by spatial and temporal frequencies.The method defines Fourier spaces, derives the smoother’s iteration matrix and Fourier symbol, and analyzes its eigenvalues.
- Frequency ranges: Semi-coarsening in time and full space-time coarsening use different low- and high-frequency ranges.These ranges determine which frequencies the smoother must damp for each coarsening strategy.
- Smoothing factor: The block-Jacobi spectral radius is expressed using α(θx, µ), which depends on the spatial frequency, discretization parameter, and Padé approximation.The analysis defines α through the (pt, pt + 1) subdiagonal Padé approximation of the exponential function.
- Smoothing estimates: Optimal damping parameters yield asymptotic smoothing bounds for semi-coarsening and full coarsening, with full coarsening requiring sufficiently small α(θx, µ).For full space-time coarsening, effective damping across all high frequencies imposes a restriction on µ through α(θx, µ).
- Two-grid convergence: The two-grid cycle converges for every µ with semi-coarsening, whereas full space-time coarsening converges when µ is sufficiently large and produces a smaller coarse problem.Theoretical convergence factors agree closely with numerical results for both coarsening strategies.
4. Numerical examples.
The numerical examples evaluate multigrid convergence across coarsening strategies, spatial and temporal discretizations, and time-polynomial degrees. Iteration counts remain bounded across mesh sizes, time-step sizes, numbers of time steps, and time ansatz functions.
- Coarsening strategy: The multigrid algorithm selects full space-time coarsening when µL ≥ µ∗ and semi-coarsening in time when µL < µ∗.The coarsening strategy changes the discretization parameter across levels and combines both approaches to reach coarser space-time levels.
- Multigrid iterations: Example 4.1 studies a three-dimensional heat problem with P1 spatial finite elements and piecewise linear discontinuous time ansatz functions.The simulation interval is (0, 1), the initial spatial decomposition has 12 tetrahedra, and the coarsest time level uses one time step.
- Multigrid iterations: The solver uses a damped block Jacobi smoother and stops at a relative error reduction of εMG = 10^-8.Each diagonal block is approximated with one geometric multigrid V-cycle.
- Multigrid iterations: Iteration numbers stay bounded independently of the spatial mesh size hLx, time-step size τLt, and number of time steps NLt = 2^Lt.This observation is reported for the convergence study in Example 4.1.
- High-order time discretizations: Iteration numbers remain bounded independently of the time-discretization ansatz functions for different polynomial degrees pt.Example 4.2 uses a two-dimensional spatial domain, τ = 1, and a simulation interval with T = 1024.
5. Parallelization.
The method parallelizes across time because its damped block Jacobi smoother operates on time blocks independently, while each spatial block can use a parallel multigrid cycle. Experiments report constant weak-scaling costs, strong scaling close to ideal halving, and increasing advantage over forward substitution.
- Parallel implementation: The damped block Jacobi smoother can execute in parallel across time, and the spatial multigrid cycles for individual time steps can also run in parallel.This enables parallelization of the full space-time problem in both temporal and spatial directions.
- Weak scaling: Weak-scaling experiments keep two time steps per core while increasing both the number of cores and time steps.The computational cost per space-time multigrid cycle remains nearly the same for each core; only communication costs grow with the hierarchy.
- Weak scaling: Weak-scaling computational costs stay completely constant as the number of cores increases, while multigrid iterations remain bounded.The space-time solver is faster than forward substitution with two cores and increasingly outperforms it at larger core counts.
- Strong scaling: The strong-scaling test fixes 32,768 time steps, producing a system with 979,238,912 unknowns.The fixed problem size is used while increasing the number of cores.
- Strong scaling: Strong-scaling computational costs are divided by a factor very close to two when the number of cores doubles.Runs on one, two, and four cores exceeded the machine's 24-hour wall-clock limit.
6. Conclusions.
The paper introduces and analyzes a space-time multigrid method for the heat equation, using local Fourier analysis to estimate convergence and parameters. Its implementation achieves strong and weak scaling, and the method is reported as applicable beyond the heat equation.
- Contributions: The method is analyzed for the heat equation using local Fourier mode analysis to estimate two-grid convergence and parameters.The paper reports that the asymptotic analysis predicts the algorithm's performance well.
- Contributions: The parallel implementation gives excellent weak and strong scaling results on a large number of processors.This is stated as a principal conclusion of the numerical and parallel studies.
- Scope: The algorithm is applicable to general parabolic problems, not only the heat equation.The paper states that it has also been successfully applied to time-dependent Stokes equations with similar speed-up results.
- Scope: The technique has also been successfully applied to parabolic control problems, but their analysis and results are deferred elsewhere.This marks the boundary of what is analyzed in the paper.