Inverse of sum of two marices, one being diagonal and other unitary.

Solution 1:

I think that you cannot expect better than a complexity $\sim n^3$.

Indeed i) $(A+D)^{-1}=D^{-1}(I+AD^{-1})^{-1}$. (it's not better using the Woodbury identity).

All the calculations are in $O(n^2)$, except the calculation of $(I+U)^{-1}$ where $U=AD^{-1}$.

or ii) $(A+D)^{-1}=A^*(I+DA^*)^{-1}$. Here all is in $O(n^2)$ except the calculations of $(I+V)^{-1}$, where $V=DA^*$, and of the product of the result by $A^*$.

Then the problem reduces to the calculation of $(I+W)^{-1}$ where $W$ is, roughly speaking, a polar form. Then $W$, a priori, has no particularity. Then the complexity of the previous calculation is $\sim n^3$.

Remark. The hypothesis $||W||<1$ is absolutely useless; to believe the opposite is an urban legend. Indeed $(I+W)^{-1}\approx I-W+W^2-W^3$ has already a complexity $\sim 2n^3$.