Cholesky Decomposition

Why No Row Swaps Are Needed

Let $A\in\mathbb{R}^{n\times n}$ be symmetric positive definite, meaning

x^TAx>0\qquad\text{for every }x\neq0

For a matrix with this condition, LU decomposition can proceed without row swaps. In exact arithmetic, $every elimination pivot is 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:

\begin{aligned} A &= A^T \\ &= (L \cdot U)^T \\ &= (L \cdot D \cdot \tilde{U})^T \\ &= \tilde{U}^T \cdot D \cdot L^T \end{aligned}

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

\tilde{U} = \begin{pmatrix} 1 & \frac{u_{12}}{u_{11}} & \cdots & \frac{u_{1n}}{u_{11}} \\ & \ddots & \ddots & \vdots \\ & & 1 & \frac{u_{n-1,n}}{u_{n-1,n-1}} \\ 0 & & & 1 \end{pmatrix}

When $L$ and $\tilde U$ have unit diagonals, this $\mathrm{LU}$ decomposition is unique. Comparing the two factorizations gives

A = L \cdot U = \tilde{U}^T \cdot (D \cdot L^T)

Define the diagonal square-root matrix as follows.

D^{\frac{1}{2}} = \begin{pmatrix} \sqrt{u_{11}} & & 0 \\ & \ddots & \\ 0 & & \sqrt{u_{nn}} \end{pmatrix}

This matrix satisfies $D^{\frac{1}{2}} \cdot D^{\frac{1}{2}} = D$ .

The Unique Lower Triangular Factor

Every real symmetric positive definite matrix $A \in \mathbb{R}^{n \times n}$ has a unique Cholesky factor with positive diagonal entries:

A = L \cdot D \cdot L^T = \tilde{L} \cdot \tilde{L}^T

The matrix $\tilde{L} = L \cdot D^{\frac{1}{2}}$ is nonsingular and lower triangular. The positive square roots of the pivots fix the signs of its diagonal and $make the Cholesky factor unique$ .

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

\tilde L=\begin{pmatrix}\tilde l_{11}&0&\cdots&0\\\tilde l_{21}&\tilde l_{22}&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\\tilde l_{n1}&\tilde l_{n2}&\cdots&\tilde l_{nn}\end{pmatrix}

This computation uses 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}$ .

\tilde{l}_{11} := \sqrt{a_{11}}

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

\tilde l_{ii}:=\sqrt{a_{ii}-\sum_{k=1}^{i-1}\tilde l_{ik}^2}

Compute the remaining entry first:

r_{ji}=a_{ji}-\sum_{k=1}^{i-1}\tilde l_{jk}\tilde l_{ik}

The second recurrence applies for $j = i + 1, \ldots, n$ .

The $expression under each square root$ must remain positive. A zero or negative value means that the input is not positive definite or that rounding has affected a nearly singular problem. Replacing that value with its absolute value changes the recurrence and can produce a factor that does not satisfy $A=LL^T$ .

After running the algorithm, we obtain the lower triangular Cholesky factor:

\tilde L=\begin{pmatrix}\tilde l_{11}&0&\cdots&0\\\tilde l_{21}&\tilde l_{22}&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\\tilde l_{n1}&\tilde l_{n2}&\cdots&\tilde l_{nn}\end{pmatrix}

Factoring a Two by Two Positive Definite Matrix

Factor the matrix

A=\begin{pmatrix}4&2\\2&5\end{pmatrix}

The entries of the lower triangular factor follow directly from the algorithm:

\tilde l_{11}=\sqrt4=2

Thus

\tilde L=\begin{pmatrix}2&0\\1&2\end{pmatrix}

Once the factor is known, solve $Ax=b$ through $two triangular systems$ : first $\tilde Ly=b$ , then $\tilde L^Tx=y$ . This avoids computing a matrix inverse.

Cholesky Algorithm Complexity

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

\frac{1}{3}n^3 + O(n^2)\quad\text{flops}

This expression gives the number of arithmetic operations.

The leading count contains about $n^3/6$ multiplications and $n^3/6$ additions. Together they give about $n^3/3$ floating-point operations, roughly half the $2n^3/3$ leading cost of $\mathrm{LU}$ factorization for a general dense matrix. Cholesky saves work by $using symmetry$ and storing only one triangular half of the factorization.