Improved ParaDiag via low-rank updates and interpolation
From MaRDI portal
Publication:6093393
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)
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.
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
Cites work
- scientific article; zbMATH DE number 3489473 (Why is no real title available?)
- scientific article; zbMATH DE number 1077997 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 3317231 (Why is no real title available?)
- 50 years of time parallel time integration
- A Direct Time Parallel Solver by Diagonalization for the Wave Equation
- A New Iterative Method for Solving Large-Scale Lyapunov Matrix Equations
- A Proposal for Toeplitz Matrix Calculations
- A Unified Analysis Framework for Iterative Parallel-in-Time Algorithms
- A ``parareal in time discretization of PDE's
- A direct solver for time parallelization
- A fast block \(\alpha\)-circulant preconditoner for all-at-once systems from wave equations
- Adaptive rational Krylov subspaces for large-scale dynamical systems
- An error analysis for rational Galerkin projection applied to the Sylvester equation
- Analysis of the Parareal Time‐Parallel Time‐Integration Method
- Block \(\omega\)-circulant preconditioners for the systems of differential equations
- Bounds on the singular values of matrices with displacement structure
- Computational Methods for Linear Matrix Equations
- Convergence analysis of a \textit{periodic-like} waveform relaxation method for initial-value problems via the diagonalization technique
- Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case
- Fast singular value decay for Lyapunov solutions with nonnormal coefficients
- Generalized Rational Krylov Decompositions with an Application to Rational Approximation
- Generalized circulant Strang-type preconditioners.
- Low-Rank Updates and a Divide-And-Conquer Method for Linear Matrix Equations
- Matrix equation techniques for certain evolutionary partial differential equations
- Multishift Variants of the QZ Algorithm with Aggressive Early Deflation
- Near-circularity for the rational Zolotarev problem in the complex plane
- Numerical solution of large and sparse continuous time algebraic matrix Riccati and Lyapunov equations: a state of the art survey
- On a Zolotarev problem in the method of alternating directions
- On the ADI method for Sylvester equations
- On the decay rate of Hankel singular values and related issues
- Optimal rational functions for the generalized Zolotarev problem in the complex plane
- PARAEXP: a parallel integrator for linear initial-value problems
- Parallelization in time through tensor-product space-time solvers
- Parallelization of the rational Arnoldi algorithm
- Preconditioning and Iterative Solution of All-at-Once Systems for Evolutionary Partial Differential Equations
- Rational Krylov for Stieltjes matrix functions: convergence and pole selection
- Rational Krylov sequence methods for eigenvalue computation
- Solution of large scale evolutionary problems using rational Krylov subspaces with optimized shifts
- Solving ordinary differential equations. II: Stiff and differential-algebraic problems.
- The ADI model problem
- The Numerical Solution of Parabolic and Elliptic Differential Equations
- The Spectrum of Circulant-Like Preconditioners for Some General Linear Multistep Formulas for Linear Boundary Value Problems
- The exponentially convergent trapezoidal rule
- The numerical range is a \((1+\sqrt{2})\)-spectral set
- Time parallelization for nonlinear problems based on diagonalization
- Toward parallel coarse grid correction for the parareal algorithm
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)
