Cholesky solves Hermitian positive-definite systems and has about half the factorisation cost of LU

By [L2] and [L3], the equation $Ax=b$ is $L{L}^{\ast }x=b$. Solve $Ly=b$ by forward substitution and then $L^{\ast }x=y$ by backward substitution. Stepwise uniqueness in [L1] makes both solves unique, and substituting $y=L^{\ast }x$ back into the first equation gives $Ax=b$.

The solve cost is the sum of two triangular solves, so [L1] gives $2(n+\frac{n(n-1)}{2}+\frac{n(n-1)}{2})=2n^2+O(n)$ scalar operations, or $n^2+O(n)$ multiply-add pairs.

In the dense factorisation, column $k$ computes one square root, $n-1-k$ divisions in the column below the pivot, and updates the trailing symmetric submatrix of size $n-1-k$ by a rank-one outer product. That update touches $\frac{(n-1-k)(n-k)}{2}$ stored entries, and each one costs one multiplication and one subtraction, so the update work is $(n-1-k)(n-k)\mathrm{.}$ Summing with $m=n-1-k$ gives ${\sum }_{m=0}^{n-1}m(m+1)=\frac{1}{3}n(n-1)(n+1)=\frac{1}{3}{n}^3+O(n^2),$ which dominates the cost. LU performs the same style of update on the full trailing matrix, giving $2{\sum }_{m=0}^{n-1}{m}^2=\frac{1}{3}n(n-1)(2n-1)=\frac{2}{3}{n}^3+O(n^2)$ scalar operations. Thus Cholesky uses about half the factorisation work.

Step 1.1 proves the solve statement, while steps 1.2 and 2.1 give the operation counts.