Improved ParaDiag via low-rank updates and interpolation
From MaRDI portal
(Redirected from Publication:6093393)
Iterative numerical methods for linear systems (65F10) Numerical methods for matrix equations (65F45) Numerical solution of discretized equations for initial value and initial-boundary value problems involving PDEs (65M22) Control/observation systems governed by partial differential equations (93C20)
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
- 50 years of time parallel time integration
- A ``parareal in time discretization of PDE's
- A direct solver for time parallelization
- A Direct Time Parallel Solver by Diagonalization for the Wave Equation
- A fast block -circulant preconditoner for all-at-once systems from wave equations
- 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
- 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 circulant Strang-type preconditioners.
- Generalized Rational Krylov Decompositions with an Application to Rational Approximation
- 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?)
- 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 exponentially convergent trapezoidal rule
- The numerical range is a \((1+\sqrt{2})\)-spectral set
- 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
- Time parallelization for nonlinear problems based on diagonalization
- Toward parallel coarse grid correction for the parareal algorithm
Cited in
(7)- A New ParaDiag Time-Parallel Time Integration Method
- Parallel-in-time solver for the all-at-once Runge-Kutta discretization
- Lifting Sylvester equations: singular value decay for non-normal coefficients
- Stage-parallel implicit Runge-Kutta methods via low-rank matrix equation corrections
- Efficient direct space-time finite element solvers for the wave equation in second-order formulation
- Time parallelization for hyperbolic and parabolic problems
- Diagonalization-based algorithms for all-at-once systems arising from linear delay differential equations
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)
