the Cholesky factorization

Some matrices have a special, friendly structure — they are symmetric (the same across the diagonal) and positive-definite (loosely, they curve upward in every direction, like a bowl). For these, the general LU machinery is overkill. The Cholesky factorization is the tailored, more efficient route: it writes such a matrix as A = L L^T, a lower-triangular matrix L times its own transpose. One triangular factor does the whole job because the symmetry means L^T is just the mirror image of L.

Because L appears twice, you only compute and store half as much, and the work is about n^3 / 3 flops — half the 2 n^3 / 3 of LU. The entries are built directly: the diagonal of L comes from a square root, l_jj = sqrt(a_jj - sum of squares of earlier entries in row j), and the off-diagonals from a division by that diagonal. To solve A x = b you do the usual pair of triangular solves: forward substitution L y = b, then back substitution L^T x = y. A beautiful bonus is that Cholesky needs NO pivoting: for a genuinely symmetric positive-definite matrix the pivots are automatically positive and the factorization is unconditionally backward stable.

Cholesky is everywhere a symmetric positive-definite matrix appears: least-squares normal equations A^T A, covariance matrices in statistics, stiffness matrices in finite elements, and as the inner solve of many optimization methods. There is a closely related variant, the LDL^T factorization, that avoids the square roots and extends to symmetric matrices that are not positive-definite. The crucial caveat: Cholesky only works for symmetric positive-definite matrices, and in fact attempting it is a cheap, reliable TEST for positive-definiteness — if a negative number turns up under a square root, the matrix is not positive-definite and the algorithm rightly fails.