2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Nick Alger
    Commented Oct 7, 2016 at 9:02

1 Answer 1

Reset to default
1
$\begingroup$

You can always try a conjugate gradient (https://en.wikipedia.org/wiki/Conjugate_gradient_method). Once you have found the solution via LU, if the new changes affect only to a small number of equations (or even a large one), the convergence should be very fast. Here it is clearly explained how to do it: ftp://ftp.numerical.rl.ac.uk/pub/talks/isd_stanford50.pdf

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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") $\endgroup$
    – Federico Poloni
    Commented Sep 7, 2016 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.