Take the 2-minute tour ×
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.

$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 '13 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 '13 at 16:34
4  
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 '13 at 2:05
2  
Jed, I think you should promote your comment to an answer here. –  Michael Grant Mar 27 '13 at 0:41
add comment

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

This question came from our site for people studying math at any level and professionals in related fields.

Your Answer

 
discard

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