The extended global Lanczos method, Gauss–Radau quadrature, and matrix function approximation

Abstract The need to evaluate expressions of the form I ( f ) ≔ trace ( W T f ( A ) W ) , where the matrix A ∈ R n × n is symmetric, W ∈ R n × k with 1 ≤ k ≪ n , and f is a function defined on the convex hull of the spectrum of A , arises in many applications including network analysis and machine learning. When the matrix A is large, the evaluation of I ( f ) by first computing f ( A ) may be prohibitively expensive. In this situation it is attractive to compute an approximation of I ( f ) by first applying a few steps of a global Lanczos-type method to reduce A to a small matrix and then evaluating f at this reduced matrix. The computed approximation can be interpreted as a quadrature rule. The present paper generalizes the extended global Lanczos method introduced in Bentbib et al. (2018) and discusses the computation of error-bounds and error estimates. Numerical examples illustrate the performance of the techniques described.