Re-using LU factorization within iterative (?) setup for a sum of two matrices

Question

So, I would love to make at least some use of my preexisting data, no matter how small, and just out of ideas. Maybe I am just a prisoner of a Kahneman-like theatre-ticket paradox, and don't know whether I should accept the losses and move on.

---

Consider a system of linear equations (in a very simplified form): $$ \begin{equation} \underbrace{(A_1+A_2)}_{M}x=b \label{eq1} \tag{1} \end{equation} $$ Here, $A_{1,2},M\in \mathbb C^{n\times n}$ dense matrices, and $x,b\in \mathbb C^n$. All three, $A_1$, $A_2$, and $M=A_1+A_2$ are nicely invertable.

We already have LU decompositions of $A_{1,2}$: $$ A_1=L_1U_1\quad A_2=L_2U_2 \label{eq2} \tag{2} $$

It is well known that computing the LU decomposition of $M$ can not really benefit from those precomputed LU's $\eqref{eq2}$, as it is certainly not even close to a low-rank update. It's a full-blown full-rank update without any particularly nice structure to it. So, I do not have any hope of arriving to an LU decomposition of $M$ using $L_{1,2},U_{1,2}$.

Note, $n$ is large and none of the matrices $A_{1,2},L_{1,2},U_{1,2}$ are stored directly in a dense format. That does not really matter for the purpose of this question other than re-constructing $M$ from scratch might be more efficient than computing it via $A_1+A_2$.

Natural solutions with obvious downsides:

1. Compute $M$ (in whatever way you want), perform its LU decomposition and solve directly.
2. Use an iterative method to solve and perform matrix-vector products with $A_1$ and $A_2$ separately without ever constructing $M$.

Now, I wonder if there is something I can do with already computed $\{L_1, U_1\}$ and $\{L_2, U_2\}$ instead of just throwing them straight into the garbage bin. For example, can I use both of them in a preconditioner(s) in some way or find weird use inside the iterative method itself? I would be happy with any possible usage of the factorization that I already have.

I tried to use $\{L_1, U_1\}$ and $\{L_2, U_2\}$ separately as left preconditioners for GMRES; however, they both performed significantly worse (as expected) compared to a much simpler preconditioner (based on $M$) I usually use. The number of iterations is quite high, so there is a lot of room for preconditioner improvement.

Any other ideas regarding possible re-usage are certainly welcomed. Even if it does not lead directly to the solution of the system $\eqref{eq1}$, but can reveal some information about $M$ and its properties cheap.

Answer 1

One thing you might not have considered trying is using a sequence of alternating solutions to two linear systems. Rather than solving

$$ (A_1+A_2)x=b, $$

you could instead try solving

$$ A_1x=b-A_2x $$ $$ A_2x=b-A_1x $$

The idea is that you'd start with some initial guess $x_0$, and then calculate a sequence of prospective solutions by doing

$$ x_1=A_1^{-1}(b-A_2x_0) $$ $$ x_2=A_2^{-1}(b-A_1x_1) $$ $$ x_3=A_1^{-1}(b-A_2x_2) $$

...and so on.

This may or may not be a good idea; this sort of thing works well sometimes in solving nonlinear equations, but I've never tried it in this context. It may not converge, or if it does converge, it may take many iterations. But since you already have the LU decompositions of $A_1$ and $A_2$, then maybe it will still be faster than a single solve with $M$ even if it takes many iterations.

Since you have some preconditioner $P\approx M^{-1}$, you might also be able to use that to get a better-than-random initial guess by doing $x_0=Pb$.