Advances in polynomial and rational Krylov methods for matrix functions with applications

In this thesis we explore the use of polynomial and rational Krylov subspace methods for the computation of the action of a matrix function $f(A)$ on a vector $b$, a crucial linear algebra task in numerous applications, focusing on both theoretical analysis and algorithmic aspects.We establish a priori and a posteriori bounds for the error in the approximation of $f(A) b$ and $b^T f(A) b$ with polynomial and rational Krylov subspace methods, by exploiting integral representations of the function $f$.We also consider the use of rational Krylov methods for approximating the action of a generalized matrix function on a vector, extending previous approaches based on the Golub-Kahan bidiagonalization and providing a convergence analysis for this approach, which directly generalizes the established theory of rational Krylov methods for standard matrix functions.We then develop a low-memory method for the computation of $f(A) b$ for a Hermitian matrix $A$, by combining an outer Lanczos method with an inner rational Krylov subspace, which is used to compress the outer basis. The inner subspace is generated using small projected matrices, and it is thus inexpensive to construct compared to the cost of the outer iteration.Next, we employ a rational Krylov method to solve a fractional diffusion equation on a graph, whose solution is given as $f(A) b$, where $A$ is the Laplacian of the graph and $f$ is a function with a branch cut on $(-infty, 0]$. We introduce techniques to cheaply remove the eigenvalue zero of the graph Laplacian, which causes delays in the convergence of Krylov subspace methods.We then consider two applications of Krylov subspace methods in the context of the approximation of $trace(f(A))$ with stochastic trace estimators or probing methods.We first address the problem of approximating the von Neumann entropy of a symmetric positive semidefinite matrix $A$, defined as $S(A) = trace(-A log A)$, and we analyze in detail the convergence of the probing method, providing both theoretical error bounds and heuristic estimates.Next, we analyze the problem of identifying gaps in the spectrum of a symmetric matrix $A$, by computing traces of spectral projectors with a combination of a stochastic trace estimator and the Lanczos method. We give a rigorous analysis of the proposed algorithm to maximize its efficiency and provide guarantees on its results.