Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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
share|improve this answer
    
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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.