Low-Rank Updates and a Divide-And-Conquer Method for Linear Matrix Equations
From MaRDI portal
Abstract: Linear matrix equations, such as the Sylvester and Lyapunov equations, play an important role in various applications, including the stability analysis and dimensionality reduction of linear dynamical control systems and the solution of partial differential equations. In this work, we present and analyze a new algorithm, based on tensorized Krylov subspaces, for quickly updating the solution of such a matrix equation when its coefficients undergo low-rank changes. We demonstrate how our algorithm can be utilized to accelerate the Newton method for solving continuous-time algebraic Riccati equations. Our algorithm also forms the basis of a new divide-and-conquer approach for linear matrix equations with coefficients that feature hierarchical low-rank structure, such as HODLR, HSS, and banded matrices. Numerical experiments demonstrate the advantages of divide-and-conquer over existing approaches, in terms of computational time and memory consumption.
Recommendations
- Low-rank updates and divide-and-conquer methods for quadratic matrix equations
- Low-Rank Updates of Matrix Functions II: Rational Krylov Methods
- Low-rank updates of matrix functions
- Divide and conquer low-rank preconditioners for symmetric matrices
- On the low rank solutions for linear matrix inequalities
- Divide-and-conquer methods for functions of matrices with banded or hierarchical low-rank structure
- Novel alternating update method for low rank approximation of structured matrices
- A rank-one updating approach for solving systems of linear equations in the least squares sense
- On optimality of approximate low rank solutions of large-scale matrix equations
- A fast and efficient algorithm for low-rank approximation of a matrix
Cites work
- A mixed-precision algorithm for the solution of Lyapunov equations on hybrid CPU-GPU platforms
- A Multigrid Method to Solve Large Scale Sylvester Equations
- A New Iterative Method for Solving Large-Scale Lyapunov Matrix Equations
- A superfast structured solver for Toeplitz linear systems via randomized sampling
- Accuracy and Stability of Numerical Algorithms
- Algorithm 432 [C2]: Solution of the matrix equation AX + XB = C [F4]
- An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
- An error analysis for rational Galerkin projection applied to the Sylvester equation
- Approximation of 1/x by exponential sums in [1, ∞)
- Approximation of Large-Scale Dynamical Systems
- Computational Methods for Linear Matrix Equations
- Convergence analysis of the extended Krylov subspace method for the Lyapunov equation
- Direct methods and ADI‐preconditioned Krylov subspace methods for generalized Lyapunov equations
- Distributed Control: A Sequentially Semi-Separable Approach for Spatially Heterogeneous Linear Systems
- Efficient Computation of the Solutions to Modified Lyapunov Equations
- Efficient numerical methods for non-local operators. \(\mathcal H^2\)-matrix compression, algorithms and analysis.
- Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case
- Estimates and asymptotic expansions for condenser p-capacities. The anisotropic case of segments
- Existence of a low rank or ℋ︁‐matrix approximant to the solution of a Sylvester equation
- Extended Arnoldi methods for large low-rank Sylvester matrix equations
- Factorized solution of Lyapunov equations based on hierarchical matrix arithmetic
- Fast algorithms for hierarchically semiseparable matrices
- Fast singular value decay for Lyapunov solutions with nonnormal coefficients
- Hierarchical matrices: algorithms and analysis
- Hierarchical tensor-product approximation to the inverse and related operators for high-dimensional elliptic problems
- scientific article; zbMATH DE number 3779707 (Why is no real title available?)
- scientific article; zbMATH DE number 802915 (Why is no real title available?)
- scientific article; zbMATH DE number 3317231 (Why is no real title available?)
- Introduction to algorithms.
- Krylov subspace methods for linear systems with tensor product structure
- Low-Rank Solution of Lyapunov Equations
- Lyapunov inverse iteration for identifying Hopf bifurcations in models of incompressible flow
- Matrices with hierarchical low-rank structures
- Numerical Methods for Large-Scale Lyapunov Equations with Symmetric Banded Data
- Numerical solution of large and sparse continuous time algebraic matrix Riccati and Lyapunov equations: a state of the art survey
- On the decay of the off-diagonal singular values in cyclic reduction
- On the decay rate of Hankel singular values and related issues
- On the eigenvalue decay of solutions to operator Lyapunov equations
- On the singular values of matrices with displacement structure
- Optimal rational functions for the generalized Zolotarev problem in the complex plane
- Self-generating and efficient shift parameters in ADI methods for large Lyapunov and Sylvester equations
- Sherman-Morrison-Woodbury formula for Sylvester and T-Sylvester equations with applications
- Solution of large scale algebraic matrix Riccati equations by use of hierarchical matrices
- Solving rank-structured Sylvester and Lyapunov equations
- Solving SDGE models: a new algorithm for the Sylvester equation
- Sparse solution of the Lyapunov equation for large-scale interconnected systems
- Superfast and stable structured solvers for Toeplitz least squares via randomized sampling
- Sylvester-based preconditioning for the waveguide eigenvalue problem
- The matrix sign function and computations in systems
- The numerical range is a \((1+\sqrt{2})\)-spectral set
- The ubiquitous Kronecker product
Cited in
(26)- Sparsity preserving optimal control of discretized PDE systems
- All-at-once method for variable-order time fractional diffusion equations
- An efficient, memory-saving approach for the Loewner framework
- Low-rank updates and divide-and-conquer methods for quadratic matrix equations
- Rational Krylov and ADI iteration for infinite size quasi-Toeplitz matrix equations
- Inexact methods for the low rank solution to large scale Lyapunov equations
- Novel alternating update method for low rank approximation of structured matrices
- Rational Krylov for Stieltjes matrix functions: convergence and pole selection
- A Krylov subspace method for the approximation of bivariate matrix functions
- Low-Rank Updates of Matrix Functions II: Rational Krylov Methods
- A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity
- Divide-and-conquer methods for functions of matrices with banded or hierarchical low-rank structure
- Low-rank updates of balanced incomplete factorization preconditioners
- Hm-toolbox: MATLAB software for HODLR and HSS matrices
- Fast solvers for two-dimensional fractional diffusion equations using rank structured matrices
- Bounds on the singular values of matrices with displacement structure
- Improved ParaDiag via low-rank updates and interpolation
- Training very large scale nonlinear SVMs using alternating direction method of multipliers coupled with the hierarchically semi-separable kernel approximations
- Iterative and doubling algorithms for Riccati‐type matrix equations: A comparative introduction
- Accelerating structural dynamics simulations with localised phenomena through matrix compression and projection-based model order reduction
- Compression properties for large Toeplitz-like matrices
- Mixed precision HODLR matrices
- A low-rank global Krylov squared Smith method for solving large-scale Stein matrix equation
- On certain classes of nonlinear matrix equations: theory, applications, and numerical solution
- A nested divide-and-conquer method for tensor Sylvester equations with positive definite hierarchically semiseparable coefficients
- Quasi-optimal hierarchically semi-separable matrix approximation
This page was built for publication: Low-Rank Updates and a Divide-And-Conquer Method for Linear Matrix Equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4631413)
