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.
How to calculate the cost of Cholesky decomposition?
3 Answers
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
- $(m-1)$ divisions
- $\dfrac13m(m^2-1)$ multiplications
- $\dfrac13m(m^2-1)$ subtractions
-
0Since 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 DUPLICATE – 2012-10-22
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.