A Block Krylov Method to Compute the Action of the Fréchet Derivative of a Matrix Function on a Vector with Applications to Condition Number Estimation

We design a block Krylov method to compute the action of the Frechet derivative of a matrix function on a vector using only matrix-vector products, i.e., the derivative of $f(A)b$ when $A$ is subject to a perturbation in the direction $E$. The algorithm we derive is especially effective when the direction matrix $E$ in the derivative is of low rank, while there are no such restrictions on $A$. Our results and experiments are focused mainly on Frechet derivatives with rank 1 direction matrices. Our analysis applies to all functions with a power series expansion convergent on a subdomain of the complex plane which, in particular, includes the matrix exponential. We perform an a priori error analysis of our algorithm to obtain rigorous stopping criteria. Furthermore, we show how our algorithm can be used to estimate the 2-norm condition number of $f(A)b$ efficiently. Our numerical experiments show that our new algorithm for computing the action of a Frechet derivative typically requires a small number of ite...

• Publication year

  2017

• Venue

  SIAM Journal on Scientific Computing

• Publication date

  2017-08-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/16M1077969
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Robust Linear Stability Analysis and a New Method for Computing the Action of the Matrix Exponential

  2018cited by this paper
• Estimating the condition number of f(A)b

  2015influential reference
• Exponential integrators for stiff elastodynamic problems

  2014cited by this paper
• Rational Krylov approximation of matrix functions: Numerical methods and optimal pole selection

  2013influential reference
• Comparison of software for computing the action of the matrix exponential

  2013cited by this paper
• The university of Florida sparse matrix collection

  2011influential reference
• Computing the Action of the Matrix Exponential, with an Application to Exponential Integrators

  2011cited by this paper
• Exponential integrators

  2010cited by this paper
• Network Properties Revealed through Matrix Functions

  2010cited by this paper
• Communicability betweenness in complex networks

  2009cited by this paper
• Functions of matrices - theory and computation

  2008cited by this paper
• Iterative methods for sparse linear systems

  2003cited by this paper
• Interpolating discrete advection – di usion propagators at Leja sequences

  2003cited by this paper
• Implementation for LAPACK of a Block Algorithm for Matrix 1-Norm Estimation

  2001influential reference
• A Block Algorithm for Matrix 1-Norm Estimation, with an Application to 1-Norm Pseudospectra

  2000influential reference
• Exponential Integrators for Large Systems of Differential Equations

  1998cited by this paper
• Analysis of some Krylov subspace approximations to the matrix exponential operator

  1992influential reference
• Implementation aspects of band Lanczos algorithms for computation of eigenvalues of large sparse sym

  1979cited by this paper
• THE UNIVERSITY OF FLORIDA.

  year unknowninfluential reference

• Challenges in computing matrix functions

  2024cites this paper
• The Fréchet derivative of the tensor t-function

  2023cites this paper
• Higher order derivatives of matrix functions

  2023cites this paper
• Sensitivity of matrix function based network communicability measures: Computational methods and a priori bounds

  2023cites this paper
• Integral representations for higher-order Fréchet derivatives of matrix functions: Quadrature algorithms and new results on the level-2 condition number

  2022cites this paper
• The complex step approximation to the higher order Fréchet derivatives of a matrix function

  2020influential citation
• Computing low‐rank approximations of the Fréchet derivative of a matrix function using Krylov subspace methods

  2020influential citation
• Forma de Jordan de la derivada de Fréchet de funciones matriciales

  2018influential citation
• Learning Heat Diffusion Graphs

  2016cites this paper