The Lanczos method for matrix function approximation

Tyler Chen


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 A\mathbf{A} applied to a vector v\mathbf{v}; i.e. from the so-called Krylov subspace generated by A\mathbf{A} and v\mathbf{v}.

The dimension kk Krylov subspace Kk\mathcal{K}_k generated by A\mathbf{A} and v\mathbf{v} is defined as Kk=Kk(A,v):=span{v,Av,,Ak1v}={p(A)v:deg(p)<k}. \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 {qi}i=0k\{ \mathbf{q}_i \}_{i=0}^{k} for the Krylov subspace Kk+1\mathcal{K}_{k+1} such that, for all i=0,1,,ki = 0, 1, \ldots, k, span{q0,q1,,qi}=Ki+1. \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,,k1i = 0,1, \ldots,k-1, Aqi=βi1qi1+αiqi+βiqi+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 q1=0\mathbf{q}_{-1} = \mathbf{0} and β1=0\beta_{-1} = 0. The coefficients {αi}i=0k1\{ \alpha_i \}_{i=0}^{k-1} and {βi}i=0k1\{ \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 AQ=QT+βk1qkek1T \mathbf{A} \mathbf{Q} = \mathbf{Q} \mathbf{T} + \beta_{k-1} \mathbf{q}_k \mathbf{e}_{k-1}^\mathsf{T} where Q:=[q0q1qk1],T:=[α0β0β0α1βk2βk2αk1]. \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(A)bf(\mathbf{A})\mathbf{b} from Kk\mathcal{K}_k using the output of the Lanczos algorithm. In particular, the Lanczos-FA iterate is defined as lank(f):=Qf(T)QTb. \mathsf{lan}_k(f) := \mathbf{Q} f(\mathbf{T}) \mathbf{Q}^\mathsf{T}\mathbf{b}.

Error bounds