Rational Matrix Functions and Rank-1 Updates
Daniel S. Bernstein, Charles F. Van Loan · SIAM Journal on Matrix Analysis and Applications · 2000
Suppose f=p/q is a quotient of two polynomials and that p has degree r p and q has degree r q . Assume that f(A) and f(A+uv T ) are defined where $A \in {\mathbb R}^{n \times n}$, $u \in {\mathbb R}^n$, and $v \in {\mathbb R}^n$ are given and set r = max{r p ,r q ). We show how to compute f(A+uv T ) in O(rn 2 ) flops assuming that f(A) is available together with an appropriate factorization of the "denominator matrix" q(A). The central result can be interpreted as a generalization of the well-known Sherman--Morrison formula. For an application we consider a Jacobian computation that arises in an inverse problem involving the matrix exponential. With certain assumptions the work required to set up the Jacobian matrix can be reduced by an order of magnitude by making effective use of the rank-1 update formulae developed in this paper.