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?

  • $\begingroup$ Maybe I'm missing something, but I'm wondering who gave this a +1? $\endgroup$ – suvrit Dec 1 '16 at 17:46
  • 3
    $\begingroup$ Reverse the order of rows and columns, and you turn a lower triangular factorization to an upper... $\endgroup$ – Robert Israel Dec 1 '16 at 19:08

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

  • $\begingroup$ Is it possible to apply proposed approach in order to find a matrix $B$ such that: $A=BB^T$? where $B$ is the positive definite matrix? $\endgroup$ – Nick Dec 6 '16 at 8:25
  • $\begingroup$ @Nick I don't think so. Is $B$ supposed to symmetric? For the symmetric root, you could consider the eigen value decomposition of $A$. $\endgroup$ – user251257 Dec 6 '16 at 8:36
  • $\begingroup$ I have only one assumption on $B$, it's should be the positive definite matrix. $\endgroup$ – Nick Dec 6 '16 at 8:40
  • $\begingroup$ How do you get the Cholesky factorization from $A=UU^T$? $\endgroup$ – Ion Sme Jun 11 '18 at 4:15

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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.