# Diagonal update of a symmetric positive definite matrix

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

-

## migrated from math.stackexchange.comJan 23 '13 at 15:51

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

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

Latest version of CHOLMOD SuiteSparse package (beta SuiteSparse 4.4.5) has a matlab (and C) API for modifying a symmetric row/column (rank2 update) for $LDL^T$ decomposition (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$

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.

-