Cholesky factorization

linear-algebra, math

Before we introduce the Cholesky factorization, let’s define some of the key words that will be used. Let ACn×nA \in \mathbb{C}^{n \times n}.

  • AA is Hermitian if A=AA^{\ast} = A, where AA^{\ast} is the conjugate transpose of AA, i.e. [A]ij=Aji[A^{\ast}]_{ij} = \overline{A_{ji}}. Note that if AA is real, then AA being Hermitian just means that AA is symmetric.
  • AA is positive definite if xTAx>0x^T A x > 0 for all x0x \neq 0. In the case of AA begin real, this is equivalent to AA having only positive (real) eigenvalues.

Given a Hermitian positive definite matrix, we can find its unique Cholesky factorization

A=LL,A = LL^{\ast},

where LL is lower triangular. This is particularly important in the context of solving linear systems. Suppose we’d like to solve the system Ax=bAx=b. If AA is Hermition positive definite, then

Ax=b    LLx=b.Ax = b \quad \implies \quad LL^{\ast}x = b.

To find our solution, we first solve the system Ly=bLy = b for yy using forward substitution, and then solve Lx=yL^{\ast}x = y for xx using backward substitution. This procedure yields a straightforward direct solve technique.

Note that the Cholesky decomposition is a case of the more general LU decomposition, which factors a matrix into a product of a lower and upper triangular matrix, because LL^{\ast} is an upper triangular matrix. However, if the matrix being factored is Hermitian positive definite, then the Cholesky factorization is preferred as it is computationally cheaper (taking advantage of symmetry) and is more stable without the need to pivot (taking advantage of positive definiteness).

There is a variant of the classic Cholesky factorization, which is the decomposition

A=LDL,A = LDL^{\ast},

where LL is a lower unit triangular matrix (the diagonal elements are all 1s), and DD is a diagonal matrix. The advantage of this variant is that the factorization algorithm avoids computing square roots. However, in the context of solving linear systems, this factorization yields the same solution technique.

© 2024 Peter Cheng