# How to calculate the cost of Cholesky decomposition?

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.

-

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
-
R_{j,j:m} = R_{j,j:m} - R_{k,j:m} \bar{R}_{kj}/R_{kk} part is not clear, can you write it in mathematical way instead of programming? –  ASROMA Oct 21 '12 at 2:45
the total cost you calculated gives us ~ 2m^3/3 not m^3/3 –  ASROMA Oct 22 '12 at 0:51
@ASROMA Usually the multiplications dominate subtraction or addition. So $m^3/3$ multiplications is what is reported usually. –  user17762 Oct 22 '12 at 0:53
Since you answered to this question, can you also answer to mine with less programming formulas, try to explain this from mathematical point of view. And you know where is my question asked, thanks... i would really appreciate it. YOU MENTIONED IT AS DUPLICATE –  ASROMA Oct 22 '12 at 1:00

To analyze complexity for Cholesky decomposition of $n \times n$ matrix, let $f(n)$ be the cost of decomposition of $n \times n$ matrix

Then,

$f(n) = 2(n-1)^2 + (n-1) + 1 + f(n-1)$ , if we use rank 1 update for $A_{22} - L_{12}L_{12}^T$.

But, since we are only interested in lower triangular matrix, only lower triangular part need to be updated which requires approximately $\frac{n}{2} flops$.

So, $f(n) = (n-1)^2 + (n-1) + 1 + f(n-1)$

$f(1) = 1$

After solving this you get $f(n) = \frac{1}{3}n^3 + \frac{2}{3}n$ , which is approximately the total cost of Cholesky decomposition.

-