The Lanczos method for matrix function approximation

Tyler Chen

Introduction

The algorithms we study in this thesis fall into a general class of algorithms called Krylov subspace methods (KSMs). KSMs produce approximations using information from the set of low-degree polynomials in $\mathbf{A}$ applied to a vector $\mathbf{v}$; i.e. from the so-called Krylov subspace generated by $\mathbf{A}$ and $\mathbf{v}$.

The dimension $k$ Krylov subspace $\mathcal{K}_k$ generated by $\mathbf{A}$ and $\mathbf{v}$ is defined as $$\mathcal{K}_{k} =\mathcal{K}_{k}(\mathbf{A},\mathbf{v}) := \operatorname{span}\{\mathbf{v}, \mathbf{A}\mathbf{v}, \ldots, \mathbf{A}^{k-1}\mathbf{v} \} = \{ p(\mathbf{A})\mathbf{v} : \deg(p) < k \}.$$

The Lanczos algorithm produces an orthonormal basis $\{ \mathbf{q}_i \}_{i=0}^{k}$ for the Krylov subspace $\mathcal{K}_{k+1}$ such that, for all $i = 0, 1, \ldots, k$, $$\operatorname{span}\{ \mathbf{q}_0, \mathbf{q}_1, \ldots, \mathbf{q}_{i} \} = \mathcal{K}_{i+1}.$$ These basis vectors satisfy a three term recurrence, for all $i = 0,1, \ldots,k-1$, $$\mathbf{A} \mathbf{q}_i = \beta_{i-1}\mathbf{q}_{i-1} + \alpha_i \mathbf{q}_i + \beta_i \mathbf{q}_{i+1}$$ with initial conditions $\mathbf{q}_{-1} = \mathbf{0}$ and $\beta_{-1} = 0$. The coefficients $\{ \alpha_i \}_{i=0}^{k-1}$ and $\{ \beta_i \}_{i=0}^{k-1}$ defining the three term recurrence are also generated by the algorithm. This recurrence can be written in matrix form as $$\mathbf{A} \mathbf{Q} = \mathbf{Q} \mathbf{T} + \beta_{k-1} \mathbf{q}_k \mathbf{e}_{k-1}^\mathsf{T}$$ where $$\mathbf{Q} := \begin{bmatrix} |&|&&|\\ \mathbf{q}_0 & \mathbf{q}_1 & \cdots & \mathbf{q}_{k-1}\\ |&|&&|\\ \end{bmatrix} ,\quad \mathbf{T} := \begin{bmatrix} \alpha_0 & \beta_0 \\ \beta_0 & \alpha_1 & \ddots & \phantom{\ddots}\\ &\ddots & \ddots & \beta_{k-2} \\ &&\beta_{k-2} & \alpha_{k-1} \\ \end{bmatrix}.$$

The algorithm

The Lanczos method for matrix function approximation (Lanczos-FA) produces an approximation to $f(\mathbf{A})\mathbf{b}$ from $\mathcal{K}_k$ using the output of the Lanczos algorithm. In particular, the Lanczos-FA iterate is defined as $$\mathsf{lan}_k(f) := \mathbf{Q} f(\mathbf{T}) \mathbf{Q}^\mathsf{T}\mathbf{b}.$$

Error bounds