Low-rank updates of matrix functions

DOI10.1137/17M1140108MaRDI QIDQ5373925zbMATH OpenOpenAlexFDO

Authors Daniel Kressner, Marcel Schweitzer, Bernhard Beckermann

Publication date 6 April 2018

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.03045

zbMATH Keywords

graph communicabilityKrylov subspace methodlow-rank updateMarkov functionmatrix exponentialmatrix functiontensorized Krylov subspace

Mathematics Subject Classification ID

Matrix exponential and similar functions of matrices (15A16) Numerical integration (65D30) Numerical computation of matrix exponential and similar matrix functions (65F60)

Abstract: We consider the task of updating a matrix function $f(A)$ when the matrix $Ain{mathbbC}^{nimesn}$ is subject to a low-rank modification. In other words, we aim at approximating $f(A+D)-f(A)$ for a matrix $D$ of rank $klln$. The approach proposed in this paper attains efficiency by projecting onto tensorized Krylov subspaces produced by matrix-vector multiplications with $A$ and $A^{\ast }$. We prove the approximations obtained from $m$ steps of the proposed methods are exact if $f$ is a polynomial of degree at most $m$ and use this as a basis for proving a variety of convergence results, in particular for the matrix exponential and for Markov functions. We illustrate the performance of our method by considering various examples from network analysis, where our approach can be used to cheaply update centrality and communicability measures.

Recommendations

• Low-Rank Updates of Matrix Functions II: Rational Krylov Methods
• Rational matrix functions and rank-1 updates
• Low rank update of singular values
• Functions and eigenvectors of partially known matrices with applications to network analysis
• Relationship between the characteristic polynomial and the spectrum of a diagonalizable matrix and those of its low-rank update

Cites work

• A mixed-precision algorithm for the solution of Lyapunov equations on hybrid CPU-GPU platforms
• An Iterative Method for Nonsymmetric Systems with Multiple Right-Hand Sides
• Analysis of Some Krylov Subspace Approximations to the Matrix Exponential Operator
• Analysis of the symmetric Lanczos algorithm with reorthogonalization methods
• Bounds for the entries of matrix functions with applications to preconditioning
• Computational Methods for Linear Matrix Equations
• Convergence of Restarted Krylov Subspace Methods for Stieltjes Functions of Matrices
• Error Estimates and Evaluation of Matrix Functions via the Faber Transform
• Functions of Matrices
• scientific article; zbMATH DE number 4211373 (Why is no real title available?)
• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• scientific article; zbMATH DE number 3482665 (Why is no real title available?)
• scientific article; zbMATH DE number 3565290 (Why is no real title available?)
• scientific article; zbMATH DE number 1960598 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• Krylov subspace methods for linear systems with tensor product structure
• Krylov Subspace Methods for Solving Large Unsymmetric Linear Systems
• Matrices, moments and quadrature with applications
• Matrices, moments and quadrature. II: How to compute the norm of the error iterative methods
• Methods of conjugate gradients for solving linear systems
• Network properties revealed through matrix functions
• Numerical range and functional calculus in Hilbert space
• On Faber polynomials and Faber expansions
• On Improving Linear Solver Performance: A Block Variant of GMRES
• On Krylov Subspace Approximations to the Matrix Exponential Operator
• On the Faber Transform and Efficient Numerical Rational Approximation
• On the stability of network indices defined by means of matrix functions
• Quadrature rule-based bounds for functions of adjacency matrices
• Ranking hubs and authorities using matrix functions
• Rational matrix functions and rank-1 updates
• Superlinear convergence of the rational Arnoldi method for the approximation of matrix functions
• The block conjugate gradient algorithm and related methods
• The computation of bounds for the norm of the error in the conjugate gradient algorithm
• The Kreiss Matrix Theorem on a General Complex Domain
• The Lanczos and conjugate gradient algorithms in finite precision arithmetic
• The numerical range is a \((1+\sqrt{2})\)-spectral set
• Updating and downdating techniques for optimizing network communicability

Cited in

(20)

• Multi-fidelity meta modeling using composite neural network with online adaptive basis technique
• Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices
• Novel alternating update method for low rank approximation of structured matrices
• Rational matrix functions and rank-1 updates
• A Krylov subspace method for the approximation of bivariate matrix functions
• Low-Rank Updates and a Divide-And-Conquer Method for Linear Matrix Equations
• On the stability of network indices defined by means of matrix functions
• Low-Rank Updates of Matrix Functions II: Rational Krylov Methods
• Mittag-Leffler functions and their applications in network science
• Divide-and-conquer methods for functions of matrices with banded or hierarchical low-rank structure
• Block Krylov subspace methods for functions of matrices. II: Modified block FOM
• Norm and trace estimation with random rank-one vectors
• Low rank update of singular values
• Computing the Square Root of a Low-Rank Perturbation of the Scaled Identity Matrix
• Matrix functions in network analysis
• Sensitivity of Matrix Function Based Network Communicability Measures: Computational Methods and A Priori Bounds
• Updating Katz centrality by counting walks
• A low-memory Lanczos method with rational Krylov compression for matrix functions
• A novel Krylov subspace method for approximating Fréchet derivatives of large-scale matrix functions
• Efficient computation of f-centralities and nonbacktracking centrality for temporal networks

Describes a project that uses

Uses Software

• MMQ Toolbox
• SuiteSparse
• SparseMatrix
• mftoolbox

This page was built for publication: Low-rank updates of matrix functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5373925)