Improved ParaDiag via low-rank updates and interpolation
From MaRDI portal
Publication:6093393
DOI10.1007/S00211-023-01372-WzbMATH Open1523.65041arXiv2204.03073MaRDI QIDQ6093393FDOQ6093393
Authors: Daniel Kressner, Stefano Massei, J. L. Zhu 
Publication date: 6 October 2023
Published in: Numerische Mathematik (Search for Journal in Brave)
Abstract: This work is concerned with linear matrix equations that arise from the space-time discretization of time-dependent linear partial differential equations (PDEs). Such matrix equations have been considered, for example, in the context of parallel-in-time integration leading to a class of algorithms called ParaDiag. We develop and analyze two novel approaches for the numerical solution of such equations. Our first approach is based on the observation that the modification of these equations performed by ParaDiag in order to solve them in parallel has low rank. Building upon previous work on low-rank updates of matrix equations, this allows us to make use of tensorized Krylov subspace methods to account for the modification. Our second approach is based on interpolating the solution of the matrix equation from the solutions of several modifications. Both approaches avoid the use of iterative refinement needed by ParaDiag and related space-time approaches in order to attain good accuracy. In turn, our new algorithms have the potential to outperform, sometimes significantly, existing methods. This potential is demonstrated for several different types of PDEs.
Full work available at URL: https://arxiv.org/abs/2204.03073
Recommendations
- Low-Rank Updates and a Divide-And-Conquer Method for Linear Matrix Equations
- Low-rank approximation of linear parabolic equations by space-time tensor Galerkin methods
- A direct solver for time parallelization
- Diagonalization-based parallel-in-time algorithms for parabolic PDE-constrained optimization problems
- Multilevel space-time block diagonal preconditioners for parabolic problems
Iterative numerical methods for linear systems (65F10) Control/observation systems governed by partial differential equations (93C20) Numerical solution of discretized equations for initial value and initial-boundary value problems involving PDEs (65M22) Numerical methods for matrix equations (65F45)
Cites Work
- Solving ordinary differential equations. II: Stiff and differential-algebraic problems.
- PARAEXP: a parallel integrator for linear initial-value problems
- Generalized Rational Krylov Decompositions with an Application to Rational Approximation
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computational Methods for Linear Matrix Equations
- A ``parareal in time discretization of PDE's
- Title not available (Why is that?)
- Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case
- The Numerical Solution of Parabolic and Elliptic Differential Equations
- A New Iterative Method for Solving Large-Scale Lyapunov Matrix Equations
- Adaptive rational Krylov subspaces for large-scale dynamical systems
- Rational Krylov sequence methods for eigenvalue computation
- On the ADI method for Sylvester equations
- Block \(\omega\)-circulant preconditioners for the systems of differential equations
- Numerical solution of large and sparse continuous time algebraic matrix Riccati and Lyapunov equations: a state of the art survey
- The exponentially convergent trapezoidal rule
- The ADI model problem
- Generalized circulant Strang-type preconditioners.
- Analysis of the Parareal Time‐Parallel Time‐Integration Method
- 50 years of time parallel time integration
- A Proposal for Toeplitz Matrix Calculations
- On the decay rate of Hankel singular values and related issues
- Solution of large scale evolutionary problems using rational Krylov subspaces with optimized shifts
- Optimal rational functions for the generalized Zolotarev problem in the complex plane
- An error analysis for rational Galerkin projection applied to the Sylvester equation
- Fast singular value decay for Lyapunov solutions with nonnormal coefficients
- Low-Rank Updates and a Divide-And-Conquer Method for Linear Matrix Equations
- Multishift Variants of the QZ Algorithm with Aggressive Early Deflation
- Title not available (Why is that?)
- Parallelization in time through tensor-product space-time solvers
- Toward parallel coarse grid correction for the parareal algorithm
- 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
- Time parallelization for nonlinear problems based on diagonalization
- Near-circularity for the rational Zolotarev problem in the complex plane
- On a Zolotarev problem in the method of alternating directions
- Parallelization of the rational Arnoldi algorithm
- The Spectrum of Circulant-Like Preconditioners for Some General Linear Multistep Formulas for Linear Boundary Value Problems
- The numerical range is a \((1+\sqrt{2})\)-spectral set
- Bounds on the singular values of matrices with displacement structure
- Matrix equation techniques for certain evolutionary partial differential equations
- Convergence analysis of a \textit{periodic-like} waveform relaxation method for initial-value problems via the diagonalization technique
- A direct solver for time parallelization
- A fast block \(\alpha\)-circulant preconditoner for all-at-once systems from wave equations
- Rational Krylov for Stieltjes matrix functions: convergence and pole selection
- A Unified Analysis Framework for Iterative Parallel-in-Time Algorithms
Cited In (3)
This page was built for publication: Improved ParaDiag via low-rank updates and interpolation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6093393)
