21
$\begingroup$

$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$?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – Joe
    Jan 16, 2013 at 0:38
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Brian Borchers
    Jan 23, 2013 at 16:34
  • 10
    $\begingroup$ 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?. $\endgroup$
    – Jed Brown
    Jan 24, 2013 at 2:05
  • 5
    $\begingroup$ Jed, I think you should promote your comment to an answer here. $\endgroup$
    – Michael Grant
    Mar 27, 2013 at 0:41

1 Answer 1

Reset to default
3
$\begingroup$

Latest version of CHOLMOD SuiteSparse package (beta 4.4.5) supports modifying a symmetric row/column (rank2 update) for $LDL^T$ decomposition, using a matlab (and C) API. I used it successfully in one of my projects.

You can use it to make $nnz(G)$ updates to the factorization. It is based on this paper.

Therefore, the complexity will be $O(nnz(G)*nnz(L))$. Where $nnz(L)$ can be significantly reduced when using a fill reducing permutation for a sparse $A$

The package can be downloaded from here

Below are some notes the package owner gave (Prof. Tim Davis):

API:

LD = ldlrowmod (LD,k) deletes row/column k, by setting A(:,k) and A(k,:) to the kth row/col of identity.

LD = ldlrowmod (LD,k,C) replaces the kth row/col of A (which must be the kth row/col of identity) with the sparse column C.

Complexity:

The row add/delete takes at most $O(nnz(L))$ time, so if $nnz(L)$ is $O(n)$, then the time is at most $O(n)$.

Fill reducing permutation:

Rarely is it a good idea to factorize a user's matrix, as in $LDL^T$ = A. Rather, we permute to $LDL^T$ = $PAP^T$ so that $L$ has vastly fewer nonzeros.

Improve this answer
$\endgroup$

Your Answer

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