Inverse or approximation to the inverse of a sum of block diagonal and diagonal matrix I need to calculate $(A+B)^{-1}$, where $A$ and $B$ are two square, very sparse and very large. $A$ is block diagonal, real symmetric and positive definite, and I have access to $A^{-1}$ (which in this case is also sparse, and block diagonal). $B$ is diagonal and real positive. In my application, I need to calculate the inverse of the sum of these two matrices where the inverse of the non-diagonal one (e.g. $A^{-1}$) is updated frequently, and readily available.
Since $B$ is full rank, the Woodbury lemma is of no use here (well, it is, but it's too slow). Other methods described in this nice question are of no use in my case as the spectral radius of $A^{-1}B$ is much larger than one. Methods based on a diagonalisation assume that it is the diagonal matrix that is being updated frequently, whereas that's not my case (i.e., diagonalising $A$ is expensive, and I'd have to do that very often).
I'm quite happy to live with an approximate solution.

Unless I am seriously mistaken, the above answer is incorrect. In my opinion, the problem lies with 
$$
A_i+diag(a_{i,1},\cdots,a_{i,n_i})=P_i\begin{bmatrix}
\lambda_{i,1}+a_{n_i}  & 0     & 0      & \cdots       & 0     & 0 \\
0  & \ddots & \ddots & \ddots &        & 0 \\\
0 & \ddots & \ddots & \ddots & \ddots &   \vdots \\
\vdots   & \ddots & \ddots & \ddots & \ddots & 0  \\
0  &        & \ddots & \ddots & \ddots & 0 \\
0 & 0      &  \cdots     & 0     & 0      & \lambda_{i,n_{i}}+a_{i,n_i}
\end{bmatrix}{P_i}^{T}
$$
Let's consider 
$$
P=\frac{1}{\sqrt{5}}\left[\begin{matrix} 2 & -1 \\ 1 & 2\end{matrix}\right]
$$
$$
D=\left[\begin{matrix} 2 & 0 \\ 0 & 1\end{matrix}\right] 
$$
$$
B= \left[\begin{matrix} 2 & 0 \\ 0 & 1\end{matrix}\right]
$$
Quick calculations show
$$
A + B = PAP^T + B = \left[\begin{matrix} 3.8 & 0.4 \\ 0.4 & 2.2\end{matrix}\right],
$$
but
$$
P ( D + B) P' = \left[\begin{matrix} 3.6 & 0.8 \\ 0.8 & 2.4\end{matrix}\right].
$$
The problem lies in the fact that adding an element to the diagonal of an un-transformed matrix A is not the same as adding it to the diagonal of the diagonalization matrix, i.e.
$$P A P^T + B \neq P (A + B) P^T$$
in general.
Or am I missing something?
PS: Unfortunately, I do not have enough reputation to comment. Sorry for the second answer, please feel free to add this to the original.
