Cholesky Decomposition

Problem

Perform Cholesky decomposition of a symmetric positive-definite matrix. Decompose matrix A into L * L^T where L is a lower triangular matrix.

Solution

from typing import List

def cholesky_decomposition(
    matrix: List[List[float]]
) -> List[List[float]]:
    n = len(matrix)
    L = [[0.0] * n for _ in range(n)]

    for i in range(n):
        for j in range(i + 1):
            s = sum(L[i][k] * L[j][k] for k in range(j))

            if i == j:
                val = matrix[i][i] - s
                if val <= 0:
                    raise ValueError("Matrix is not positive definite")
                L[i][j] = val ** 0.5
            else:
                L[i][j] = (matrix[i][j] - s) / L[j][j]

    return L

Explanation

1. For each element L[i][j] where j <= i (lower triangular):
2. - Diagonal (i == j): L[i][i] = sqrt(A[i][i] - sum(L[i][k]^2 for k < i)). The value under the root must be positive for the matrix to be positive definite.
3. - Off-diagonal (i > j): L[i][j] = (A[i][j] - sum(L[i][k]*L[j][k] for k < j)) / L[j][j].
4. The decomposition is unique for positive-definite matrices with positive diagonal entries in L.
5. Result satisfies A = L * L^T.

Complexity

• Time: O(n^3 / 3), roughly half the cost of LU decomposition
• Space: O(n^2) for the L matrix