Error Bounds for Lanczos-Based Matrix Function Approximation

DOI10.1137/21M1427784MaRDI QIDQ5863878zbMATH OpenOpenAlexFDO

Authors Tyler Chen, Cameron Musco, Christopher Musco, Anne Greenbaum

Publication date 3 June 2022

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.09806

zbMATH Keywords

LanczosKrylov subspace methodmatrix function approximation

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Analysis of algorithms and problem complexity (68Q25) Numerical computation of matrix exponential and similar matrix functions (65F60)

Abstract: We analyze the Lanczos method for matrix function approximation (Lanczos-FA), an iterative algorithm for computing $f(mathbfA)mathbfb$ when $mathbfA$ is a Hermitian matrix and $mathbfb$ is a given vector. Assuming that $f:mathbbCightarrowmathbbC$ is piecewise analytic, we give a framework, based on the Cauchy integral formula, which can be used to derive a priori and a posteriori error bounds for Lanczos-FA in terms of the error of Lanczos used to solve linear systems. Unlike many error bounds for Lanczos-FA, these bounds account for fine-grained properties of the spectrum of $mathbfA$, such as clustered or isolated eigenvalues. Our results are derived assuming exact arithmetic, but we show that they are easily extended to finite precision computations using existing theory about the Lanczos algorithm in finite precision. We also provide generalized bounds for the Lanczos method used to approximate quadratic forms $mathbf{b}^{e}xtsfHf(mathbfA)mathbfb$, and demonstrate the effectiveness of our bounds with numerical experiments.

Recommendations

• Error bounds for the Lanczos methods for approximating matrix exponentials
• 2-norm error bounds and estimates for Lanczos approximations to linear systems and rational matrix functions
• Estimating the error in matrix function approximations
• Error bounds in the simple Lanczos procedure for computing functions of symmetric matrices and eigenvalues
• Stability of the Lanczos method for matrix function approximation
• A computable error bound for matrix functionals
• Theoretical error bounds and general analysis of a few Lanczos-type algorithms
• The extended global Lanczos method for matrix function approximation
• Uniform Error Estimates for the Lanczos Method

Cites work

• scientific article; zbMATH DE number 1049350 (Why is no real title available?)
• scientific article; zbMATH DE number 3219899 (Why is no real title available?)
• scientific article; zbMATH DE number 2222870 (Why is no real title available?)
• 2-norm error bounds and estimates for Lanczos approximations to linear systems and rational matrix functions
• A Divide-and-Conquer Algorithm for the Symmetric Tridiagonal Eigenproblem
• A comparison of limited-memory Krylov methods for Stieltjes functions of Hermitian matrices
• A posteriori error estimates of Krylov subspace approximations to matrix functions
• A restarted Lanczos approximation to functions of a symmetric matrix
• A study of defect-based error estimates for the Krylov approximation of \(\varphi\)-functions
• Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem
• Accuracy of the Lanczos process for the eigenproblem and solution of equations
• Accurate error estimation in CG
• Analysis of Some Krylov Subspace Approximations to the Matrix Exponential Operator
• Approximating the extreme Ritz values and upper bounds for the \(A\)-norm of the error in CG
• Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences
• Comparison of splittings used with the conjugate gradient algorithm
• Computable upper error bounds for Krylov approximations to matrix exponentials and associated \(\varphi\)-functions
• Computational methods for UV-suppressed fermions
• Computing A^\alpha, \log(A), and Related Matrix Functions by Contour Integrals
• Convergence of Restarted Krylov Subspace Methods for Stieltjes Functions of Matrices
• Efficient and stable Arnoldi restarts for matrix functions based on quadrature
• Efficient estimation of eigenvalue counts in an interval.
• Error Analysis of the Lanczos Algorithm for Tridiagonalizing a Symmetric Matrix
• Error bounds and estimates for Krylov subspace approximations of Stieltjes matrix functions
• Error bounds in the simple Lanczos procedure for computing functions of symmetric matrices and eigenvalues
• Estimating the Attainable Accuracy of Recursively Computed Residual Methods
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Euclidean-norm error bounds for SYMMLQ and CG
• Exponential Integrators for Large Systems of Differential Equations
• Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature
• Functions of Matrices
• Krylov subspace approximation of eigenpairs and matrix functions in exact and computer arithmetic
• Matrices, moments and quadrature with applications
• Methods of conjugate gradients for solving linear systems
• Numerical methods for the QCDd overlap operator. I: Sign-function and error bounds
• On Estimating the Largest Eigenvalue with the Lanczos Algorithm
• On Krylov Subspace Approximations to the Matrix Exponential Operator
• On error estimation in the conjugate gradient method and why it works in finite precision computations
• Predicting the Behavior of Finite Precision Lanczos and Conjugate Gradient Computations
• Relations between Galerkin and Norm-Minimizing Iterative Methods for Solving Linear Systems
• Stability of the Lanczos method for matrix function approximation
• Stopping Criteria for Rational Matrix Functions of Hermitian and Symmetric Matrices
• The Lanczos and conjugate gradient algorithms in finite precision arithmetic
• The exponentially convergent trapezoidal rule
• Two polynomial methods of calculating functions of symmetric matrices
• Using Nonorthogonal Lanczos Vectors in the Computation of Matrix Functions

Cited in

(19)

• Bounds on the transformed errors of solutions to SLAEs with ill-conditioned matrices
• Error bounds and estimates for Krylov subspace approximations of Stieltjes matrix functions
• Stability of the Lanczos method for matrix function approximation
• Krylov-Aware Stochastic Trace Estimation
• A posteriori error estimate for computing \(\operatorname{tr}(f(A))\) by using the Lanczos method.
• scientific article; zbMATH DE number 7404607 (Why is no real title available?)
• Dimension Free Nonasymptotic Bounds on the Accuracy of High-Dimensional Laplace Approximation
• Near-optimal convergence of the full orthogonalization method
• Estimation of spectral gaps for sparse symmetric matrices
• Randomized block-Krylov subspace methods for low-rank approximation of matrix functions
• Low-Memory Krylov Subspace Methods for Optimal Rational Matrix Function Approximation
• Preconditioning without a preconditioner using randomized block Krylov subspace methods
• scientific article; zbMATH DE number 4149448 (Why is no real title available?)
• Theoretical error bounds on the convergence of the Lanczos and block-Lanczos methods
• Optimal polynomial approximation to rational matrix functions using the Arnoldi algorithm
• A residual based error estimate for Leja interpolation of matrix functions
• A posteriori error bounds for the block-Lanczos method for matrix function approximation
• Estimating the error in matrix function approximations
• Error Estimates and Evaluation of Matrix Functions via the Faber Transform

Describes a project that uses

Uses Software

• MNIST

This page was built for publication: Error Bounds for Lanczos-Based Matrix Function Approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5863878)