Cholesky Decomposition

For a symmetric positive-definite matrix A, the Cholesky decomposition finds a lower triangular matrix L such that A = LLᵀ. The diagonal entries of L are strictly positive. This is a specialized and highly efficient variant of LU decomposition, exploiting symmetry to halve both storage and computation. The algorithm is non-iterative and completes in a fixed number of floating-point operations, making it deterministic and predictable for real-time grid applications.

The primary use in probabilistic power flow is transforming independent standard normal samples into correlated samples with a target covariance matrix Σ.

• Compute the Cholesky decomposition: Σ = LLᵀ
• Generate a vector z of independent samples from N(0,1)
• The correlated vector is x = μ + Lz This ensures that Cov(x) = L × Cov(z) × Lᵀ = LILᵀ = Σ, preserving the exact correlation structure between wind farms, solar plants, and load buses.

The matrix must be symmetric positive-definite for the decomposition to exist and be numerically stable. A matrix is positive-definite if xᵀAx > 0 for all non-zero vectors x. In power systems, covariance matrices constructed from valid correlation coefficients and positive variances naturally satisfy this. However, near-singularity can occur with highly correlated renewable sites, requiring ridge regularization (adding a small diagonal term λI) to restore positive-definiteness before factorization.

Cholesky decomposition requires approximately n³/3 floating-point operations for an n×n matrix, compared to 2n³/3 for standard LU decomposition. This 2x speedup is critical when generating thousands of Monte Carlo scenarios for large transmission networks. The algorithm also requires only half the memory since only the lower triangle is stored. For a 1000-bus system, this reduces memory from ~8 MB to ~4 MB for the covariance matrix.

For symmetric positive-definite matrices, Cholesky decomposition is numerically stable without pivoting. The diagonal entries remain positive throughout factorization, avoiding the division-by-zero risks that plague general LU decomposition. However, pivot-free stability depends on the condition number of the matrix. Ill-conditioned covariance matrices—common when modeling highly correlated adjacent wind farms—can cause catastrophic cancellation, requiring the use of modified Cholesky algorithms that dynamically add regularization.

Cholesky decomposition is the final linear transformation step within the broader Nataf transformation pipeline. The Nataf method first maps correlated non-normal variables (e.g., Weibull-distributed wind speeds) to correlated standard normals, then uses Cholesky to decompose the intermediate correlation matrix R_z. The resulting lower triangular matrix transforms independent normals into samples that preserve the rank correlation structure of the original non-normal variables.

A symmetric, positive-definite matrix encoding the pairwise variances and correlations between multiple random variables—such as wind speeds at different farms or nodal loads. The diagonal elements represent the variance of each variable, while off-diagonal elements capture covariance. Cholesky decomposition requires this matrix to be positive-definite to guarantee a unique, real-valued lower triangular factor. In power systems, covariance matrices are estimated from historical SCADA data or spatial weather models to preserve realistic geographical correlations in Monte Carlo simulations.

The output of Cholesky decomposition: a matrix where all entries above the main diagonal are zero. Multiplying this matrix by a vector of independent standard normal samples produces a new vector with the exact target covariance structure. The sparsity pattern of L reflects the conditional independence relationships among variables. In large-scale grid problems with thousands of correlated loads, the fill-in of L directly impacts computational memory requirements and factorization speed.

A two-step procedure that extends Cholesky decomposition to handle non-normal marginal distributions with arbitrary correlation structures:

• Step 1: Transform correlated non-normal variables to correlated standard normals using the inverse CDF of each marginal distribution
• Step 2: Apply Cholesky decomposition to the intermediate normal correlation matrix This is essential in power systems where wind power follows a Weibull distribution and load follows a beta or log-normal distribution, yet spatial correlations must be preserved.

A mathematical property requiring that for any non-zero vector x, the quadratic form xᵀAx > 0. This guarantees that the covariance matrix represents a valid probability distribution and that all eigenvalues are strictly positive. In practice, estimated covariance matrices from noisy or incomplete data may lose this property. Near-positive-definite matrices require regularization techniques—such as adding a small diagonal perturbation or projecting onto the nearest positive-definite matrix—before Cholesky factorization can proceed without numerical failure.

A closely related variant that decomposes a symmetric matrix as A = LDLᵀ, where L is unit lower triangular and D is diagonal. This avoids computing square roots, making it numerically more stable for ill-conditioned covariance matrices. In probabilistic power flow, LDLᵀ is preferred when the condition number of the covariance matrix is high—common when modeling highly correlated renewable generation across geographically proximate sites. The diagonal D matrix also provides direct insight into the conditional variances of each variable.

The end-to-end workflow where Cholesky decomposition is embedded:

• Step 1: Generate a vector z of independent samples from N(0,1)
• Step 2: Compute y = Lz, where L is the Cholesky factor of the target covariance matrix Σ
• Step 3: Apply inverse marginal transformations if non-normal distributions are required
• Step 4: Feed the correlated samples into a deterministic power flow solver This pipeline is the computational engine behind Monte Carlo and Latin Hypercube probabilistic power flow studies.