Cholesky Decomposition

LU Decomposition for Positive Definite Matrices

For positive definite matrices, there is a special property that makes decomposition much simpler. LU decomposition can be performed without using a permutation matrix $P$ because Gaussian elimination can proceed without row swapping, and all pivot elements generated are guaranteed to be positive.

This means we obtain factorization in the form $A = L \cdot U$, where the diagonal elements of $U$ are positive pivot elements for all diagonal indices.

Since $A = A^T$, we also have:

where $\tilde{U}$ is a matrix whose main diagonal is normalized to 1, and $D$ is a diagonal matrix:

Since LU decomposition without $P$ is unique, then:

If we define:

then $D^{\frac{1}{2}} \cdot D^{\frac{1}{2}} = D$.

Cholesky Decomposition

Positive definite matrices $A \in \mathbb{R}^{n \times n}$ allow for Cholesky decomposition:

where $\tilde{L} = L \cdot D^{\frac{1}{2}}$ is a regular lower triangular matrix. This matrix can be computed using the Cholesky algorithm.

The computation of matrix $\tilde{L}$ is performed with:

based on the relationship $\tilde{L} \cdot \tilde{L}^T = A$. The following algorithm produces the Cholesky factor.

Cholesky Algorithm

Given a positive definite matrix $A \in \mathbb{R}^{n \times n}$.

For $i = 2, \ldots, n$:

for $j = i + 1, \ldots, n$.

After running this algorithm, we will obtain the Cholesky factor which is a lower triangular matrix:

Cholesky Algorithm Complexity

The Cholesky algorithm for computing the Cholesky factor $\tilde{L}$ from $A \in \mathbb{R}^{n \times n}$ requires:

arithmetic operations.

This is half the number of operations required to compute LU decomposition, because the use of symmetry allows us to perform computations without row swapping in a different order.