How to calculate the cost of Cholesky decomposition?

Question

The cost of Cholesky decomposition is $n^3/3$ flops (A is a $n \times n$ matrix). Could anyone show me some steps to get this number? Thank you very much.

Answer 1

We want to factor $A$ into $R^TR$ where $R$ is upper triangular. The algorithm proceeds as follows.

R = A
for k=1 to m
   for j=k+1 to m
      R_{j,j:m} = R_{j,j:m} - R_{k,j:m} \bar{R}_{kj}/R_{kk}
   R_{k,k:m} = R_{k,k:m}/\sqrt{R_{kk}}

The line inside the innermost for-loop

      R_{j,j:m} = R_{j,j:m} - R_{k,j:m} \bar{R}_{kj}/R_{kk}

requires $1$ division, $m-j+1$ multiplications and $m-j+1$ subtractions. Since $j$ runs from $k+1$ to $m$, the cost will be

$m-k$ divisions,

$\left(\displaystyle (m+1)(m-k) - \sum_{j=k+1}^m j \right) = \dfrac{(m-k)(m+k+1)}2$ multiplications and

$\left(\displaystyle (m+1)(m-k) - \sum_{j=k+1}^m j \right) = \dfrac{(m-k)(m+k+1)}2$ subtractions.

Now in the outer loop $k$ runs from $1$ to $m$ costing $(m-1)$ divisions, $\dfrac13m(m^2-1)$ multiplications and $\dfrac13m(m^2-1)$ subtractions.

Hence, the total cost for Cholesky is

1. $(m-1)$ divisions
2. $\dfrac13m(m^2-1)$ multiplications
3. $\dfrac13m(m^2-1)$ subtractions