Cholesky decompostion: upper triangular or lower triangular?

Question

Can I find and use $U$ such that

$$A = U U^{T}$$

where $U$ is an upper triangular matrix, to find a solution instead of finding $L$ such that $ A = L L^{T}$ (where $L$ is a lower triangular matrix) to solve $Ax=b$ using Cholesky factorization? If not, what is the correct way of using Cholesky factorization?

Answer 1

You can use $A=UU^T$ to solve linear equations. However it is not what people call Cholesky decomposition. Also the algorithm is less intuitive.

Note: Both decompositions are equivalent. Let $P$ the permutation which reverses the order, which is symmetric. Then, $\tilde A = PAP$ is symmetric and positive definite iff $A$ is. In particular we have the cholesky decomposition $$ \tilde A = PAP = (PUP)(PUP)^T. $$

Answer 2

For those wondering about the answer above, here's a simple python snippet to obtain such reversed cholesky:

import numpy as np

def reverse_cholesky(X):
    n = X.shape[0]
    U = np.zeros((n,n))

    for row_forward in range(n):
        row_backward = n - row_forward - 1
        for col_forward in range(row_backward, n):
            col_backward = n - col_forward + row_backward - 1
            s = 0
            for cl in range(n-1, col_backward-1, -1):
                s += U[row_backward,cl] * U[col_backward,cl]
            if row_backward == col_backward:
                U[row_backward,col_backward] = np.sqrt(
                    X[row_backward,row_backward] - s
                )
            else:
                U[row_backward,col_backward] = (
                    X[row_backward,col_backward] - s
                ) / U[col_backward,col_backward]
    return U

One can verify that it's the same as calculating the cholesky of the original matrix reversing the rows and columns, and then reversing the rows and columns in that factorization like another comment here suggested; but factorizing in reverse order directly can potentially be more efficient.

Answer 3

We can modify the original Cholesky algorithm to obtain an upper-triangular version. According to https://en.wikipedia.org/wiki/Cholesky_decomposition#The_Cholesky_algorithm, the original method starts at the top left and goes down to the bottom right by using this recursion step $A_i = L_i A_{i+1} L_i^T$, where $L_i$ is a lower-triangular matrix. The $A_i$ in the original version is created in a top-down fashion.

The upper-triangular version of the algorithm starts at the bottom right and goes up to the top left using a similar recursion $A_i = U_i A_{i+1} U_i^T$, where $U_i$ is an upper-triangular matrix. The $A_i$ matrix is created in a bottom-up fashion as $ A_{i}=\begin{bmatrix} B & b & 0 \\ b^T & a & 0 \\ 0 & 0 & I_{i-1} \end{bmatrix}.$ The $A_{i+1}$ matrix is defined as $ A_{i+1}=\begin{bmatrix} B-\frac{1}{a}bb^T & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & I_{i-1} \end{bmatrix}.$ The $U_i$ matrix is defined as $ U_{i}=\begin{bmatrix} I_{n-i} & \frac{1}{\sqrt{a}}b & 0 \\ 0 & \sqrt{a} & 0 \\ 0 & 0 & I_{i-1} \end{bmatrix}.$ We can check that this expression $A_i = U_i A_{i+1} U_i^T$ holds, which gives an upper-triangular version of the Cholesky algorithm ($A=UU^T$, where $U=U_1U_2\dots U_n$ is an upper-triangular matrix).