Near-Optimal Approximation of Matrix Functions by the Lanczos Method

MaRDI QIDQ6428568zbMATH OpenFDO

Authors Noah Amsel, Tyler Chen, Anne Greenbaum, Cameron Musco, Chris Musco

Publication date 6 March 2023

Mathematics Subject Classification ID

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

Abstract: We study the Lanczos method for approximating the action of a symmetric matrix function $f(mathbfA)$ on a vector $mathbfb$ (Lanczos-FA). For the function $mathbf{A}^{-1}$, it is known that the error of Lanczos-FA after $k$ iterations matches the error of the best approximation from the Krylov subspace of degree $k$ when $vecA$ is positive definite. We prove that the same holds, up to a multiplicative approximation factor, when $f$ is a rational function with no poles in the interval containing $mathbfA$'s eigenvalues. The approximation factor depends the degree of $f$'s denominator and the condition number of $mathbfA$, but not on the number of iterations $k$. Experiments confirm that our bound accurately predicts the convergence of Lanczos-FA. Moreover, we believe that our result provides strong theoretical justification for the excellent practical performance that has long by observed of the Lanczos method, both for approximating rational functions and functions like $mathbf{A}^{-1/2}mathbfb$ that are well approximated by rationals.

This page was built for publication: Near-Optimal Approximation of Matrix Functions by the Lanczos Method

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