2
$\begingroup$

How many elements of $LU$ decomposition of a symmetric matrix change after adding a sparse symmetric matrix? Is it more efficient to recompute $LU$ decomposition after adding a sparse matrix comparing to computing it from scratch for the sum?

More formally, let $M$ be a symmetric matrix, $L_M\cdot U_M$ its pivoted $LU$ decomposition, and $N$ a sparse symmetric matrix of the same dimension.

The 1st question was: Is it true that $M+N$ has $LU$ decomposition $L_{M+N}\cdot U_{M+N}$ such that both $L_{M+N}-L_M$ and $U_{M+N}-U_M$ are sparse?

The 2nd question: Provided that the answer to the 1st question is positive, is it possible to compute $L_{M+N}-L_M$ and $U_{M+N}-U_M$ asymptotically faster than computing $L_{M+N}$ and $U_{M+N}$ without knowledge of $L_M$ and $U_M$ would require?

$\endgroup$

1 Answer 1

2
$\begingroup$

As far as I know, there is theory available only for updating decompositions under low-rank perturbations: see [Golub, Van Loan, Matrix Computations 3rd ed., ch 12] for details on updating QR decompositions, and references to other types of updates. QRs are easier to update because there is no pivoting involved, but the theory for all of them is similar.

There are already several questions about updating LU factorizations (or LU factorizations of sums) here on MO, but usually the answer is "no unless it's low-rank".

In your case, sparse could imply low-rank if it's very sparse (only a small number of rows/columns containing nonzeros), but it is a special case.

(incidentally, why are you using LU on a symmetric matrix in the first place? There are ad-hoc methods for symmetric matrices such as LDL^T and Cholesky).

$\endgroup$
2
  • $\begingroup$ The matrix in question is a Hessian for a large optimization problem; the Hessian needs to be updated after optimization steps. $LU$ is just the 1st thing that I looked into. Which decomposition would you suggest for this? The Hessian itself if fairly sparse, and updates are even more sparse. $\endgroup$
    – Michael
    Nov 8, 2013 at 16:49
  • $\begingroup$ I suppose it's not positive definite then. First thing I'd look into is $LDL^T$, if you can find good software for that for sparse matrices (I don't know what the rest of your software stack is). I'm not an expert in sparse matrix stuff though. $\endgroup$ Nov 8, 2013 at 19:07

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.