Analysis of a New Space-Time Parallel Multigrid Algorithm for Parabolic Problems
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- A Simple Proposal for Parallel Computation Over Time of an Evolutionary Process with Implicit Time Stepping2016
- A multi-level spectral deferred correction methodBIT Numerical Mathematics, 2014
- Multilevel Block Factorization Preconditioners2008
- The Design and Implementation of hypre, a Library of Parallel High Performance Preconditioners2006
- The Parareal in Time Iterative Solver: a Further Direction to Parallel Implementation2004
- Space-time domain decomposition for parabolic problemsNumerische Mathematik, 2002
- A parareal in time procedure for the control of partial differential equationsComptes Rendus Mathematique, 2002
- Analysis of tensor product multigridNumerical Algorithms, 2001
- A waveform relaxation algorithm with overlapping splitting for reaction diffusion equationsNumerical Linear Algebra with Applications, 1999
- Multi-grid dynamic iteration for parabolic equationsBIT Numerical Mathematics, 1987