4
$\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.

2 Answers 2

3

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
    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?2012-10-21
  • 0
    the total cost you calculated gives us ~ 2m^3/3 not m^3/32012-10-22
  • 0
    @ASROMA Usually the multiplications dominate subtraction or addition. So $m^3/3$ multiplications is what is reported usually.2012-10-22
  • 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. And you know where is my question asked, thanks... i would really appreciate it. YOU MENTIONED IT AS DUPLICATE2012-10-22
3

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.