5
$\begingroup$

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.

3 Answers 3

4

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
  • 0
    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. $A$nd you know where is my question asked, thanks... i would really appreciate it. YOU MENTIONED IT AS DUPLICATE2012-10-22
4

Taken from http://www.cs.utexas.edu/users/flame/Notes/NotesOnCholReal.pdf

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.