Stability of the Lanczos method for matrix function approximation

zbMATH Open1406.65032arXiv1708.07788MaRDI QIDQ4607994FDOQ4607994

Authors: Cameron Musco, Christopher Musco, Aaron Sidford 

Publication date: 15 March 2018

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.

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

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

Mathematics Subject Classification ID

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

Cited In (16)

• Title not available (Why is that?)
• On uniform connectivity of algebraic matrix sets
• Principal component projection with low-degree polynomials
• Error Bounds for Lanczos-Based Matrix Function Approximation
• Randomized numerical linear algebra: Foundations and algorithms
• Krylov-Aware Stochastic Trace Estimation
• Stability of the Lanczos algorithm on matrices with regular spectral distributions
• Computation of generalized matrix functions with rational Krylov methods
• Low-Memory Krylov Subspace Methods for Optimal Rational Matrix Function Approximation
• Title not available (Why is that?)
• Speeding Up Krylov Subspace Methods for Computing \(\boldsymbol{{f}(A){b}}\) via Randomization
• Stability and uniqueness properties of Taylor approximations of matrix functions
• A posteriori error bounds for the block-Lanczos method for matrix function approximation
• Computable upper error bounds for Krylov approximations to matrix exponentials and associated \(\varphi\)-functions
• Near-optimal stochastic approximation for online principal component estimation
• Hardness results for structured linear systems

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)