Do there exist Conjugate-Gradient algorithms for "nested" inverses. The Conjugate Gradient algorithm (CG) is an iterative Matrix-vector multiplication based scheme for solving equations like
$$Ax = b$$
Without having to calculate an explicit inverse $A^{-1}$ or some factorization of $A$.
I wonder if we have more complicated things we would want to calculate, for example
$$(A^{-1}+C_1)(B^{-1}+C_2) x$$
Wherever we do encounter $M^{-1}v$ (if the matrix $M$ fulfills the requirements posed by the CG algorithm) we can calculate this by the CG algorithm.
While we could be certain that this approach shall work... Is it efficient or wasteful?
Do there exist some framework or expansion for CG which takes such things into account?
By linearity if we encounter $( {M_1}^{-1} + {M_2}^{-1} )v$ we can expand it like so : $${M_1}^{-1}v + {M_2}^{-1}v$$ and calculate the terms independently of each other.
If we encounter $(M_1)^{-1}(M_2)^{-1}v$ we can calculate either $$(M_1)^{-1}(M_2^{-1}v)$$ in other words a two-step calculation, or we can do $(M_2M_1)^{-1}v$ where the matrix to be inverted can be treated either lazily decoupled inside of the CG algorithm or be explicitly calculated before. Which would be most efficient?
 A: If you do an inner-outer CG method, where CG is used for the inner inverses within a CG iteration for the outer inverse, then achieving an overall error to be less than some tolerance $\epsilon$, requires you to do the inner solves to within tolerance $\epsilon$, for all outer iterations. This is typically quite expensive, and so it is not commonly done.
There are some "flexible" Krylov methods such as flexible GMRES (fGMRES), which allow you some flexibility in the tolerance for the inner solve. I've had poor results with this and do not recommend it.
I would recommend, instead, defining auxiliary variables to remove inverses, then doing a Krylov method on the overall block system that results. For example, in the equation
$$(A^{-1} + C_1)(B^{-1} + C_2)x=b$$
let us define $y:= B^{-1} x$, and $z:=A^{-1}(y + C_2 x)$. Multiplying these auxiliary variables through to clear inverses allows us to write our system as follows:
\begin{align*}
z + C_1 y + C_1 C_2x &= b \\
B y &= x \\
A z &= y + C_2 x
\end{align*}
or equivalently
$$
\begin{bmatrix}
C_1 C_2 & C_1 & I \\
-I & B & 0 \\
-C_2 & -I & A
\end{bmatrix}
\begin{bmatrix}
x \\ y \\ z
\end{bmatrix}
=
\begin{bmatrix}
b \\ 0 \\ 0
\end{bmatrix}
$$
and now this bigger 3x3 block system may be solved with a standard Krylov method like GMRES.
Typically, if the original system is symmetric and you are smart about how you define your variables and order the blocks, you can make the expanded block system symmetric, and so you can use MINRES, which saves memory as compared to GMRES. However, the way I have done it in the example above is not symmetric.
