# Can someone explain to me Cholesky decomposition to find its complexity?

I know there are some posts there explaining the complexity of Cholesky decomposition. But i have couple of questions:

1. we know that A=L*L^T (L is lower triangular matrix) is Cholesky decomposition, so what is exactly calculated to find the complexity??? The recursive part only, or everything in the decomposition?

we know that a11 = l11*l11 ; --- L21 = A21/l11; --- L21^T = A21^T/l11; --- AND at last L22*L22^T = A22 - L12*L12^T, so the complexity includes all of these components?

1. can someone WITHOUT any programming syntax, but IN NATURAL language explain to me how to calculate the Cholesky Decomposition as detailed as possible?

Thanks A lot, and please do not CLOSE this i need to clarify some points for me...

-
possible duplicate of How to calculate the cost of Cholesky decomposition? – user17762 Oct 21 '12 at 21:36
This is similar but i need different explaination. The other is not clear because of programming syntax. I was asking clear natural language ezplaination with as little math as possible – ASROMA Oct 21 '12 at 21:56
Numerical Recipes has a very good explanation of this. Its code is not production value, but as a textbook, it's perfect. – orion Mar 28 '14 at 8:28

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.

-