Documentation

# cholupdate

Rank 1 update to Cholesky factorization

## Syntax

```R1 = cholupdate(R,x) R1 = cholupdate(R,x,'+') R1 = cholupdate(R,x,'-') [R1,p] = cholupdate(R,x,'-') ```

## Description

`R1 = cholupdate(R,x)` where ```R = chol(A)``` is the original Cholesky factorization of `A`, returns the upper triangular Cholesky factor of `A + x*x'`, where `x` is a column vector of appropriate length. `cholupdate` uses only the diagonal and upper triangle of `R`. The lower triangle of `R` is ignored.

`R1 = cholupdate(R,x,'+')` is the same as `R1 = cholupdate(R,x)`.

`R1 = cholupdate(R,x,'-')` returns the Cholesky factor of `A - x*x'`. An error message reports when R is not a valid Cholesky factor or when the downdated matrix is not positive definite and so does not have a Cholesky factorization.

`[R1,p] = cholupdate(R,x,'-')` will not return an error message. If `p` is `0`, `R1` is the Cholesky factor of `A - x*x'`. If `p` is greater than `0`, `R1` is the Cholesky factor of the original `A`. If `p` is `1`, `cholupdate` failed because the downdated matrix is not positive definite. If `p` is `2`, `cholupdate` failed because the upper triangle of `R` was not a valid Cholesky factor.

## Examples

```A = pascal(4) A = 1 1 1 1 1 2 3 4 1 3 6 10 1 4 10 20 R = chol(A) R = 1 1 1 1 0 1 2 3 0 0 1 3 0 0 0 1 x = [0 0 0 1]';```

This is called a rank one update to `A` since `rank(x*x')` is `1`:

```A + x*x' ans =```
``` 1 1 1 1 1 2 3 4 1 3 6 10 1 4 10 21```

Instead of computing the Cholesky factor with ```R1 = chol(A + x*x')```, we can use `cholupdate`:

```R1 = cholupdate(R,x) R1 =```
``` 1.0000 1.0000 1.0000 1.0000 0 1.0000 2.0000 3.0000 0 0 1.0000 3.0000 0 0 0 1.4142```

Next destroy the positive definiteness (and actually make the matrix singular) by subtracting `1` from the last element of `A`. The downdated matrix is:

```A - x*x' ans = 1 1 1 1 1 2 3 4 1 3 6 10 1 4 10 19```

Compare `chol` with `cholupdate`:

```R1 = chol(A-x*x') Error using chol Matrix must be positive definite. R1 = cholupdate(R,x,'-') Error using cholupdate Downdated matrix must be positive definite.```

However, subtracting `0.5` from the last element of `A` produces a positive definite matrix, and we can use `cholupdate` to compute its Cholesky factor:

```x = [0 0 0 1/sqrt(2)]'; R1 = cholupdate(R,x,'-') R1 = 1.0000 1.0000 1.0000 1.0000 0 1.0000 2.0000 3.0000 0 0 1.0000 3.0000 0 0 0 0.7071```

## Tips

`cholupdate` works only for full matrices.

## Algorithms

`cholupdate` uses the algorithms from the LINPACK subroutines `ZCHUD` and `ZCHDD`. `cholupdate` is useful since computing the new Cholesky factor from scratch is an $O\left({N}^{3}\right)$ algorithm, while simply updating the existing factor in this way is an $O\left({N}^{2}\right)$ algorithm.

## References

 Dongarra, J.J., J.R. Bunch, C.B. Moler, and G.W. Stewart, LINPACK Users' Guide, SIAM, Philadelphia, 1979.