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?



Updating $LU$ decomposition after adding a sparse matrix
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).


