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.

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...

share|improve this question
    
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 at 8:28

1 Answer 1

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.