Randomized Sketching for Krylov Approximations of Large-Scale Matrix Functions
From MaRDI portal
Abstract: The computation of f(A)b, the action of a matrix function on a vector, is a task arising in many areas of scientific computing. In many applications, the matrix A is sparse but so large that only a rather small number of Krylov basis vectors can be stored. Here we discuss a new approach to overcome these limitations by randomized sketching combined with an integral representation of f(A)b. Two different approximations are introduced, one based on sketched FOM and another based on sketched GMRES approximation. The convergence of the latter method is analyzed for Stieltjes functions of positive real matrices. We also derive a closed form expression for the sketched FOM approximant and bound its distance to the full FOM approximant. Numerical experiments demonstrate the potential of the presented sketching approaches.
Recommendations
- Randomized Low-Rank Approximation of Monotone Matrix Functions
- A new investigation of the extended Krylov subspace method for matrix function evaluations
- A comparison of limited-memory Krylov methods for Stieltjes functions of Hermitian matrices
- Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations
- Convergence rates for inverse-free rational approximation of matrix functions
Cites work
- scientific article; zbMATH DE number 5713161 (Why is no real title available?)
- scientific article; zbMATH DE number 3565290 (Why is no real title available?)
- A Restarted Krylov Subspace Method for the Evaluation of Matrix Functions
- A black-box rational Arnoldi variant for Cauchy-Stieltjes matrix functions
- A comparison of limited-memory Krylov methods for Stieltjes functions of Hermitian matrices
- A fast randomized algorithm for overdetermined linear least-squares regression
- A fast randomized algorithm for the approximation of matrices
- A generalization of the steepest descent method for matrix functions
- A restarted Lanczos approximation to functions of a symmetric matrix
- Analysis of Some Krylov Subspace Approximations to the Matrix Exponential Operator
- Approximating the matrix exponential of an advection-diffusion operator using the incomplete orthogonalization method
- Convergence of Restarted Krylov Subspace Methods for Stieltjes Functions of Matrices
- Deflated restarting for matrix functions
- Efficient and stable Arnoldi restarts for matrix functions based on quadrature
- Extended Krylov Subspaces: Approximation of the Matrix Square Root and Related Functions
- Fast CG-Based Methods for Tikhonov--Phillips Regularization
- Functions of Matrices
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- Implementation of a restarted Krylov subspace method for the evaluation of matrix functions
- KIOPS: a fast adaptive Krylov subspace solver for exponential integrators
- Krylov Subspace Methods for Solving Large Unsymmetric Linear Systems
- Matrix functions
- Methods of conjugate gradients for solving linear systems
- Multigrid preconditioning for the overlap operator in lattice QCD
- Numerical methods for the QCDd overlap operator. I: Sign-function and error bounds
- On Restart and Error Estimation for Krylov Approximation of w=f(A)v
- On the generation of Krylov subspace bases
- Parallelizable restarted iterative methods for nonsymmetric linear systems. part I: Theory
- Preconditioning Lanczos Approximations to the Matrix Exponential
- Randomized Gram-Schmidt process with application to GMRES
- Randomized linear algebra for model reduction. I. Galerkin methods and error estimation
- Randomized linear algebra for model reduction. II: Minimal residual methods and dictionary-based approximation
- Rational Krylov approximation of matrix functions: numerical methods and optimal pole selection
- Sketching as a tool for numerical linear algebra
- Some Remarks on the Elman Estimate for GMRES
- The principle of minimized iterations in the solution of the matrix eigenvalue problem
- Two polynomial methods of calculating functions of symmetric matrices
- Variations on Arnoldi's method for computing eigenelements of large unsymmetric matrices
Cited in
(20)- Sketch-and-Restart: Randomized Sketching in Quadrature-Based Restarting for Matrix Functions
- scientific article; zbMATH DE number 7049775 (Why is no real title available?)
- GMRES with randomized sketching and deflated restarting
- Polynomial preconditioning for the action of the matrix square root and inverse square root
- Sketched and truncated polynomial Krylov subspace methods: matrix Sylvester equations
- Krylov-Aware Stochastic Trace Estimation
- A sketch-and-select Arnoldi process
- Frequent directions: simple and deterministic matrix sketching
- GP-CMRH: an inner product free iterative method for block two-by-two nonsymmetric linear systems
- Limited‐memory polynomial methods for large‐scale matrix functions
- Randomized sketching of nonlinear eigenvalue problems
- Speeding Up Krylov Subspace Methods for Computing \(\boldsymbol{{f}(A){b}}\) via Randomization
- Randomized Low-Rank Approximation of Monotone Matrix Functions
- A unified convergence analysis of random sketch methods for rank deficient linear systems
- A Fast Monte Carlo Algorithm for Evaluating Matrix Functions with Application in Complex Networks
- Randomized and inner-product free Krylov methods for large-scale inverse problems
- Approximation of functions of large matrices with Kronecker structure
- Randomized implicitly restarted Arnoldi method for the non-symmetric eigenvalue problem
- Krylov subspace recycling with randomized sketching for matrix functions
- Unified matrix analysis for strong consistency of estimators based on the singular value decomposition with orthogonal projections for noisy datasets
This page was built for publication: Randomized Sketching for Krylov Approximations of Large-Scale Matrix Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6116663)
