0
$\begingroup$

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

  • 0
    Numerical Recipes has a very good explanation of this. Its code is not production value, but as a textbook, it's perfect.2014-03-28

1 Answers 1

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.