Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 10 down vote favorite

$A$ is a $n \times n$ symmetric positive definite (SPD) sparse matrix. $G$ is a sparse diagonal matrix. $n$ is large ($n$ >10000) and the number of nonzeros in the $G$ is usually 100 ~ 1000.

$A$ has been factorized in the cholesky form as $LDL^T$.

How to update the $L$ and $D$ efficiently when $A$ becomes $A+G$?

share|improve this question
Does G have only positive elements? If so, here is a trivial upper bound: view the diagonal update as a sum of rank one updates. There exist O(n^2) methods to compute the LDL^t factorization of a rank-one update (google search provides examples). Then your diagonal update will run in O(rn^2) where r is the number of non-zero diagonal elements of G. Given the specific nature of these updates there are shortcuts to save some computations, but it's not clear if it's possible to reduce the order below O(rn^2). – Joe Jan 16 at 0:38
1  
I agree- I don't believe there's any way to do diagonal updates to a Cholesky factorization faster than just repeating the factorization, but rank one updates can be done in $O(m^2)$ time, and you only have to do one for each nonzero on the diagonal of $G$. – Brian Borchers Jan 23 at 16:34
3  
For $n \sim 10^4$ and $\mathrm{nnz}(G)$ in the hundreds, it'll be hard to beat refactoring $A$. If the size of $A$ becomes much larger and $G$ is very sparse, it could pay off. In any case, the possible updates and approximations are covered in depth by Can diagonal plus fixed symmetric linear systems be solved in quadratic time after precomputation?. – Jed Brown Jan 24 at 2:05
1  
Jed, I think you should promote your comment to an answer here. – Michael C. Grant Mar 27 at 0:41

migrated from math.stackexchange.com Jan 23 at 15:51

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.