Stability of the Lanczos method for matrix function approximation

MaRDI QIDQ4607994zbMATH OpenFDO

Authors Cameron Musco, Christopher Musco, Aaron Sidford

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1708.07788, http://dl.acm.org/citation.cfm?id=3175410

Mathematics Subject Classification ID

Numerical computation of matrix exponential and similar matrix functions (65F60) Complexity and performance of numerical algorithms (65Y20)

Abstract: The ubiquitous Lanczos method can approximate $f(A)x$ for any symmetric $nimesn$ matrix $A$, vector $x$, and function $f$. In exact arithmetic, the method's error after $k$ iterations is bounded by the error of the best degree-$k$ polynomial uniformly approximating $f(x)$ on the range $[lambd{a}_{min}(A),lambd{a}_{max}(A)]$. However, despite decades of work, it has been unclear if this powerful guarantee holds in finite precision. We resolve this problem, proving that when $ma{x}_{xin[lambd{a}_{min},lambd{a}_{max}]}|f(x)|leC$, Lanczos essentially matches the exact arithmetic guarantee if computations use roughly $log(nC|A|)$ bits of precision. Our proof extends work of Druskin and Knizhnerman [DK91], leveraging the stability of the classic Chebyshev recurrence to bound the stability of any polynomial approximating $f(x)$. We also study the special case of $f(A)=A^{-1}$, where stronger guarantees hold. In exact arithmetic Lanczos performs as well as the best polynomial approximating $1/x$ at each of $A$'s eigenvalues, rather than on the full eigenvalue range. In seminal work, Greenbaum gives an approach to extending this bound to finite precision: she proves that finite precision Lanczos and the related CG method match any polynomial approximating $1/x$ in a tiny range around each eigenvalue [Gre89]. For $A^{-1}$, this bound appears stronger than ours. However, we exhibit matrices with condition number $kappa$ where exact arithmetic Lanczos converges in $polylog(kappa)$ iterations, but Greenbaum's bound predicts $Omega(kapp{a}^{1/5})$ iterations. It thus cannot offer significant improvement over the $O(kapp{a}^{1/2})$ bound achievable via our result. Our analysis raises the question of if convergence in less than $poly(kappa)$ iterations can be expected in finite precision, even for matrices with clustered, skewed, or otherwise favorable eigenvalue distributions.

Recommendations

• Error Bounds for Lanczos-Based Matrix Function Approximation
• Using Nonorthogonal Lanczos Vectors in the Computation of Matrix Functions
• Accuracy of the Lanczos process for the eigenproblem and solution of equations
• A restarted Lanczos approximation to functions of a symmetric matrix
• Krylov subspace approximation of eigenpairs and matrix functions in exact and computer arithmetic

Cited in

(24)

• Principal component projection with low-degree polynomials
• Computable upper error bounds for Krylov approximations to matrix exponentials and associated \(\varphi\)-functions
• On uniform connectivity of algebraic matrix sets
• Stability and uniqueness properties of Taylor approximations of matrix functions
• scientific article; zbMATH DE number 4100488 (Why is no real title available?)
• Using Nonorthogonal Lanczos Vectors in the Computation of Matrix Functions
• scientific article; zbMATH DE number 7049775 (Why is no real title available?)
• Computation of generalized matrix functions with rational Krylov methods
• Hardness results for structured linear systems
• Error Bounds for Lanczos-Based Matrix Function Approximation
• Randomized numerical linear algebra: Foundations and algorithms
• Krylov-Aware Stochastic Trace Estimation
• Low-Memory Krylov Subspace Methods for Optimal Rational Matrix Function Approximation
• Stability of the Lanczos algorithm on matrices with regular spectral distributions
• Speeding Up Krylov Subspace Methods for Computing \(\boldsymbol{{f}(A){b}}\) via Randomization
• A posteriori error bounds for the block-Lanczos method for matrix function approximation
• Near-optimal stochastic approximation for online principal component estimation
• Solving sparse linear systems faster than matrix multiplication
• Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers
• Fine-grained analysis and faster algorithms for iteratively solving linear systems
• Faster algorithms for Schatten-p low rank approximation
• A low-memory Lanczos method with rational Krylov compression for matrix functions
• Preconditioning without a preconditioner using randomized block Krylov subspace methods
• Optimal near-optimality bounds for the Lanczos method for matrix functions

This page was built for publication: Stability of the Lanczos method for matrix function approximation

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