Lanczos-based matrix function computation with applications to network analysis

Thesis

Our aim in this dissertation is to study iterative methods for computing matrix functions on large, sparse, symmetric matrices and to apply these routines to a concrete problem that arises in the analysis of undirected networks: evaluating the importance of edges.

We first focus on the relationship between the Lanczos procedure in numerical linear algebra and scalar polynomial approximation. We show how connections to classical Gauss quadrature lead to efficient algorithms for computing matrix function quadratic forms, low-rank directional derivatives of the trace of a matrix function, and low-rank updates of the trace of a matrix function. We further consider the correspondence between Lanczos-based methods and polynomial interpolation for the computation of the action of a matrix function on a vector, low-rank directional derivatives, and low-rank updates. Our emphasis on connections to scalar approximation theory allows for a simple, unified presentation of these methods and their theoretical properties. Perhaps most notably, we are the first to provide characterization theorems equating the Lanczos approximants for dynamic problems—low-rank derivatives and low-rank updates—to Gauss quadrature and bivariate polynomial interpolation.

Second, we consider practical numerical experimentation and applications to network science. We conduct experiments on large matrices arising from structured networks to illustrate the low time-complexity of Lanczosbased methods for network science. As an application, we study the identification of important edges in a network. We show that matrix functions can interpolate between local degree-based and global eigenvectorbased measures, and propose an algorithm for ranking all edges of the network in time nearly-linear in the number of edges of the network by combining Lanczos-based procedures with randomized algorithms for diagonal estimation.

Authors: West, N

• DOI: 10.5287/ora-dxgqb7r85
• Type of award: MSc by Research
• Awarding institution: University of Oxford
• Language: English
• Keywords: Gauss quadrature; Lanczos procedure; Frechet derivative; edge centrality; matrix exponential; networks; low-rank updates; Krylov methods