Fast algorithms from low-rank updates
- Daniel Kressner (Ecole polytechnique fédérale de Lausanne)
Abstract
The development of efficient numerical algorithms for solving large-scale linear systems is one of the success stories of numerical linear algebra that has had a tremendous impact on our ability to perform complex numerical simulations and large-scale statistical computations. Many of these developments are based on multilevel and domain decomposition techniques, which are intimately linked to Schur complements and low-rank updates of matrices. These tools do not carry over in a direct manner to other important linear algebra problems. Two such problems are the computation of matrix functions and the solution of matrix equations. They arise in a wide variety of application areas, including control, signal processing, network analysis, and computational statistics. Despite impressive progress made during the last decades on both problems, there remain numerous situations in which existing algorithms become computationally too expensive. This includes seemingly simple tasks, such as computing the diagonal of a matrix function for a very large sparse matrix.
In this talk, we describe a new framework for performing low-rank updates of matrix functions. This allows to address a wide variety of matrix functions and matrix structures, including sparse matrices as well as matrices with hierarchical low rank and Toeplitz-like structures. The framework is quite versatile and can be adaptated to seemingly unrelated problems, such as computing and updating determinants of large-scale matrices.
The talk is based on joint work with Bernhard Beckermann and Marcel Schweitzer.