The matrix modification formula
The basic formula
Suppose we have already solved Ax = b and wish to solve a perturbed system
where ДЛ has low rank. The matrix modification formula provides a tool for solving such systems. It was defined by Sherman and Morrison (1949) for rank- one changes and was generalized by Woodbury (1950). Expressed in terms of matrix inverses it has the form
Here, ДЛ = VWT is a rank-k matrix, where V and W are n x k matrices. We are interested only in the case where k is much less than n. This formula may be readily verified and its verification is left to Exercise 15.1.
To preserve sparsity, we will use the LU factors rather than computing inverses. Moreover, we may multiply both sides of equation (15.2.2) by the right- hand side vector b to yield the relation
We see that the solution to the modified problem (Л + VWT)-1b is given as the solution to the original problem A-1b and a correction term.
While (15.2.3) may look intimidating, the computation is quite straightforward and cheap when k is much less than n. The steps are
- (i) Solve AX = V using the LU factors of A.
- (ii) Compute T = I + WTX and its LU factors.
- (iii) Solve Ay = b using the LU factors of A.
- (iv) Solve Ts = WTy using the LU factors of T.
- (v) Compute x = y — Xs.
The first step is likely to be the most expensive step. It involves O(kr') operations where т' is the number of entries in the LU factors of A. Forming WTX requires at most O(k2n) operations but, if W is sparse, it will require far less, perhaps as few as k2. The rest of step (ii) requires O(k3) operations, so will be inexpensive. Step (iii) requires 0(т') operations, step (iv) requires at most O(kn) operations, and step (v) requires O(kn) operations. Note that steps (i) and (ii) need to be performed only once if we have many vectors b.
A common case is where ДA has rank k and has nonzeros in only k rows or columns. If ДA has nonzeros in only k columns, it can be expressed in the form ДA = VWT, where V consists of those nonzero columns and WT is the submatrix of the nxn identity matrix that has 1s in the nonzero columns of ДA. If ДA has nonzeros in only k rows, we may take V to be the submatrix of I with 1s the nonzero rows of ДA and WT to consist of the nonzero rows.