A parallel-in-time collocation method using diagonalization: theory and implementation for linear problems

DOI10.2140/CAMCOS.2023.18.55arXiv2103.12571OpenAlexW4390108763MaRDI QIDQ6183191FDOQ6183191

Authors: Gayatri Čaklović, Robert Speck, Martin Frank 

Publication date: 26 January 2024

Published in: Communications in Applied Mathematics and Computational Science (Search for Journal in Brave)

Abstract: We present and analyze a parallel implementation of a parallel-in-time collocation method based on $alpha$-circulant preconditioned Richardson iterations. While many papers explore this family of single-level, time-parallel "all-at-once" integrators from various perspectives, performance results of actual parallel runs are still scarce. This leaves a critical gap, because the efficiency and applicability of any parallel method heavily rely on the actual parallel performance, with only limited guidance from theoretical considerations. Further, challenges like selecting good parameters, finding suitable communication strategies, and performing a fair comparison to sequential time-stepping methods can be easily missed. In this paper, we first extend the original idea of these fixed point iterative approaches based on $alpha$-circulant preconditioners to high-order collocation methods, adding yet another level of parallelization in time "across the method". We derive an adaptive strategy to select a new $alpha$-circulant preconditioner for each iteration during runtime for balancing convergence rates, round-off errors, and inexactness of inner system solves for the individual time-steps. After addressing these more theoretical challenges, we present an open-source space- and time-parallel implementation and evaluate its performance for two different test problems.

Full work available at URL: https://arxiv.org/abs/2103.12571

Recommendations

• scientific article; zbMATH DE number 879001
• Time-parallel iterative solvers for parabolic evolution equations
• Parallel implementation for the two-stage SDIRK methods via diagonalization
• Toward an efficient parallel in time method for partial differential equations
• A parallel-in-time implementation of the Numerov method for wave equations

zbMATH Keywords

iterative methodsdiagonalizationcollocationhigh-performance computingparallel-in-time integrationpetsc4py

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20) Roundoff error (65G50) Iterative numerical methods for linear systems (65F10) Spectral, collocation and related methods for initial value and initial-boundary value problems involving PDEs (65M70) Numerical solution of discretized equations for initial value and initial-boundary value problems involving PDEs (65M22)

Cites Work

• PARAEXP: a parallel integrator for linear initial-value problems
• Algorithm 997: pySDC -- prototyping spectral deferred corrections
• Algorithm 965: RIDC methods: a family of parallel time integrators
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• A ``parareal in time discretization of PDE's
• Stability of the Parareal Algorithm
• Toward an efficient parallel in time method for partial differential equations
• Stable parareal in time method for first- and second-order hyperbolic systems
• 50 years of time parallel time integration
• Parallel time integration with multigrid
• Interweaving PFASST and parallel multigrid
• Parallel methods for integrating ordinary differential equations
• Generalized inverses of certain Toeplitz matrices
• A high-order time-parallel scheme for solving wave propagation problems via the direct construction of an approximate time-evolution operator
• Analysis of a Krylov subspace enhanced parareal algorithm for linear problems
• Explicit parallel-in-time integration of a linear acoustic-advection system
• Volterra integral equations. An introduction to theory and applications
• Preconditioning and Iterative Solution of All-at-Once Systems for Evolutionary Partial Differential Equations
• A Direct Time Parallel Solver by Diagonalization for the Wave Equation
• Parallel methods for ODEs
• An All-at-Once Preconditioner for Evolutionary Partial Differential Equations
• Algorithm 1016
• Wave propagation characteristics of Parareal
• Convergence of parareal for the Navier-Stokes equations depending on the Reynolds number
• Applications of time parallelization
• Convergence analysis of a \textit{periodic-like} waveform relaxation method for initial-value problems via the diagonalization technique
• A diagonalization-based parareal algorithm for dissipative and wave propagation problems
• A fast block \(\alpha\)-circulant preconditoner for all-at-once systems from wave equations
• PFASST-ER: combining the parallel full approximation scheme in space and time with parallelization across the method
• A uniform spectral analysis for a preconditioned all-at-once system from first-order and second-order evolutionary problems
• Twelve ways to fool the masses when giving parallel-in-time results

Cited In (2)

• Diagonalization-based preconditioners and generalized convergence bounds for ParaOpt
• On generalized preconditioners for time-parallel parabolic optimal control

This page was built for publication: A parallel-in-time collocation method using diagonalization: theory and implementation for linear problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6183191)