# LU decomposition using two Cholesky decompositions (part two)

## Alec Jacobson

## March 04, 2012

I previously posted about how often you can compute a LU decomposition of a matrix `Q`

using two Cholesky decompositions. Specifically when your matrix is of the form:
```
Q = / A C \
\ C
```^{T} * /

In that post I assumed you had a subroutine that computes the Cholesky factorization of a symmetric positive-definite matrix `A`

:
`LL`^{T}=A

Where `L`

is a lower-triangular matrix.
Often, routines exist to give you an even better factorization which includes a permutation matrix `S`

:
`LL`^{T}=S^{T}AS

This often results in a more sparse `L`

.
Working through the LU decomposition using this type of Cholesky factorization is a bit tedious and requires some careful book keeping.
This time I want to fill in the missing parts of the following system:
```
/ ? * \ / A C \ / ? * \ = / ? * \ / ? ? \
\ * ? / \ C
```^{T} * / \ * ? / \ ? ? / \ * ? /

Since `A`

is symmetric positive definite we use our factorization `S`^{T}AS = LL^{T}

which gives us:
`/ S`^{T} * \ / A C \ / S * \ = / L * \ / L^{T} ? \
\ * ? / \ C^{T} * / \ * ? / \ ? ? / \ * ? /

But this means that know we need that `S`^{T}C = L ?

. But L is lower triangular so itâ€™s easy to compute:
`M = L`^{-1}S^{T}C

We can then place M into our LU decomposition:
`/ S`^{T} * \ / A C \ / S * \ = / L * \ / L^{T} M \
\ * ? / \ C^{T} * / \ * ? / \ M^{T} ? / \ * ? /

Now at this point we could use cholesky factorization *without* the permutation matrix to complete the missing parts, but we might as well use our better decomposition again. To do this we must be a bit careful. We want to create the zeros in the lower right corner of the system. To do this we need a factorization of M^{T}M. But our new routine gives us:
`KK`^{T} = T^{T}M^{T}MT

where `K`

another lower triangular matrix and `T`

another permutation matrix.
So we replace `M`

with `MT`

in our system and plug in `K`

. This gives us:
`/ S`^{T} * \ / A C \ / S * \ = / L * \ / L^{T} MT \
\ * ? / \ C^{T} * / \ * ? / \ T^{T}M^{T} K / \ * -K^{T} /

Finally, compute the missing pieces by evaluating the right hand side and we indeed get our original system conjugated with a permutation matrix composed of the permutation matrices from both of the cholesky factorizations:
`/ S`^{T} * \ / A C \ / S * \ = / L * \ / L^{T} MT \
\ * T^{T} / \ C^{T} * / \ * T / \ T^{T}M^{T} K / \ * -K^{T} /