Lets say I have a $(N,N)$ matrix $A$ and want to quickly calculate the inverse of an updated matrix $A' = A+D$, where $D$ is a diagonal matrix with only a few non-zero entries with positions $M = \{m_i\}$
i.e
$$ D_{i,j} = \begin{cases} d_n,& \text{if } i=j \text{ and } i,j\in M \\ 0, & \text{otherwise} \end{cases} $$
What I would like to do: quickly compute $A'^{-1}$ using $A^{-1}$ (already known) using the woodbury formula (although I am open to other solutions)
This requires a good factorisation of $D$ - my original choice was
$D = \sqrt{V}\cdot I_N \cdot V$, with $V = \sqrt{D}$
In the woodbury formula, we have
$$ (A+D)^{-1} = A^{-1} - A^{-1} V ( I_N +VA^{-1}V)^{-1}VA^{-1} $$
This is not particularly useful, as the center term $ (I_N + VA^{-1}V)$ is a $(N,N)$ matrix & so is as costly to compute as the original inverse.
It seems to me that this should be fairly straightforward to do with a better choice of factorisation for the update (or maybe via a different route), but I'm not sure what to pick for the substitute.
A better solution:
If we set e.g $M=(0,3,5)$ - that is, the nonzero diagonal entries of D, then we can do this via setting $U=V^T$, and
$$ V = \begin{bmatrix} 1 & 0&0&0&0&0\\ 0 & 0&0&1&0&0\\ 0 & 0&0&0&0&1 \end{bmatrix} $$
Then $UV^T = \text{diag}(1,0,0,1,0,1)$
This is good - we are now able to compute the $ (I_N + VA^{-1}V)$ much more efficiently, as this is a 3x3 table instead of a 6x6.
For a 1000x1000 matrix with 25 diagonal updates, I see approximately a 30x speedup with this method v.s vanilla via eigen. Any ideas for further improvements?