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
- 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 Krylov Subspace Method for the Evaluation of 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
- scientific article; zbMATH DE number 5713161 (Why is no real title available?)
- scientific article; zbMATH DE number 3565290 (Why is no real title available?)
- 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
(22)- Frequent directions: simple and deterministic matrix sketching
- scientific article; zbMATH DE number 7049775 (Why is no real title available?)
- Approximation of functions of large matrices with Kronecker structure
- Limited‐memory polynomial methods for large‐scale matrix functions
- Krylov-Aware Stochastic Trace Estimation
- Randomized Low-Rank Approximation of Monotone Matrix Functions
- Speeding Up Krylov Subspace Methods for Computing \(\boldsymbol{{f}(A){b}}\) via Randomization
- A Fast Monte Carlo Algorithm for Evaluating Matrix Functions with Application in Complex Networks
- Polynomial preconditioning for the action of the matrix square root and inverse square root
- A sketch-and-select Arnoldi process
- Randomized sketching of nonlinear eigenvalue problems
- Krylov subspace recycling with randomized sketching for matrix functions
- A unified convergence analysis of random sketch methods for rank deficient linear systems
- Randomized and inner-product free Krylov methods for large-scale inverse problems
- Randomized implicitly restarted Arnoldi method for the non-symmetric eigenvalue problem
- Unified matrix analysis for strong consistency of estimators based on the singular value decomposition with orthogonal projections for noisy datasets
- Sketched and truncated polynomial Krylov subspace methods: matrix Sylvester equations
- GMRES with randomized sketching and deflated restarting
- GP-CMRH: an inner product free iterative method for block two-by-two nonsymmetric linear systems
- Sketch-and-Restart: Randomized Sketching in Quadrature-Based Restarting for Matrix Functions
- A general framework for Krylov ODE residuals with applications to randomized Krylov methods
- An efficient energy-preserving scheme for nonlinear generalized damped space-fractional Klein-Gordon equation based on the matrix transfer technique
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)
