Conference abstracts

Session B7 - Numerical Linear Algebra

July 15, 14:30 ~ 15:00 - Room B5

Low-rank updates of matrix functions

Daniel Kressner

EPFL, Switzerland   -

This talk is concerned with the development and analysis of fast algorithms for updating a matrix function $f(A)$ if $A$ undergoes a low-rank change $A+L$. For example, when $A$ is the Laplacian of an undirected graph then removing one edge or vertex of the graph corresponds to a rank-one change of $A$. The evaluation und update of such matrix functions (or parts thereof) is of relevance in the analysis of network community structure of networks and signal graph processing. Our algorithms are based on the tensorization of polynomial or rational Krylov subspaces involving $A$ and $A^T$. The choice of a suitable element from such a tensorized subspace for approximating $f(A+L)-f(A)$ is straightforward in the symmetric case but turns out to be more intricate in the nonsymmetric case. We show that the usual convergence results for Krylov subspace methods for matrix functions can be extended to our algorithms. If time permits, we will also touch upon the closely related problem of applying the Fr├ęchet derivative of a matrix function to a low-rank matrix.

Joint work with Bernhard Beckermann, U de Lille 1, France and Marcel Schweitzer, EPFL, Switzerland.

View abstract PDF

FoCM 2017, based on a nodethirtythree design.