# Solving system of related equations without completely recomputing LU decomposition for each equation

Let $\Sigma$ be positive definite and the $D_i$ positive diagonal. Let the $X_i$ be unknown square matrices. Consider the system of equations:

$$(I+\Sigma D_i)X_i=\Sigma\hspace{5mm}\text{for}\hspace{5mm}i=1,...n.$$

Is it possible to numerically solve all of these equations without having to completely recompute the LU factorization of $(I+\Sigma D_i)$ for each $i$?

I've been messing around with the Cholesky and Eigen-decompositions of $\Sigma$, but no luck so far, I think it's probably not possible, but I thought I'd ask.

If it helps, note that the solutions $X_i$ will all be positive definite, since

$$X_i^{-1} = \Sigma^{-1} + D_i.$$

Edit:

It looks like this answer here by the all knowing Brian Borchers means that this is infact impossible.

• One situation where high-rank diagonal updates can be done cheaply is if the matrices involved are hierarchical matrices (matrix is not necessarily low rank, but it's off-diagonal blocks are low rank in a recursive manner), and you have precomputed a hierarchical representation. – Nick Alger Oct 7 '16 at 9:02

• If the new changes affect only a small number of equations, then it's a low-rank update to the LU factorization and it's easy to do it in $O(n^2)$. But the diagonal of $D$ is positive here (and I presume this means "strictly positive") – Federico Poloni Sep 7 '16 at 9:50