0
$\begingroup$

$B_{(n+1)(n+1)}$ = $ \begin{bmatrix} A & u \\ u^T & 1 \\ \end{bmatrix}$ = $\begin{bmatrix} L_{11} & 0 \\ L_{21} & l_{22} \\ \end{bmatrix} $ $\begin{bmatrix} L_{11}^T & L_{21}^T \\ 0 & l_{22} \\ \end{bmatrix} $

Here A is nxn matrix, $l_{22}$ is scalar, $L_{11}$ is also a nxn matrix. So Cholasky factorization of this B matrix will give us the following: $L_{11}*L_{11}^T=A, L_{11}*L_{21}^T=u, L_{21}*L_{11}^T=u^T$, and $L_{21}*L_{21}^T=1-l_{11}^2$

  1. What to do after this?

  2. Is the factorization done?

  3. If this is done, how can I compute B's complexity(flops) if A is given - lets say it is N?

Thanks.

  • 0
    That's basically the outer product formulation of Cholesky decomposition. Watkins's book has a discussion on this.2012-10-28

1 Answers 1

1

Well, regarding 1, $L_1$ is computed as per the standard cholesky factorisation for $A$. Then from your working, you get $L_{21}^T=L_{11}^{-1}u$ and $l_{22}=\sqrt{1-L_{21}L_{21}^T}$.

For 2, now the factorisation is complete as you have determined what they factors should be.

For 3, the complexity for the determination of $L_{11}$ is known for the Cholesky decomposition. Then you just have to increment it for the additional computations which you incur.

  • 0
    so then $L_{11}$ should be such a matrix that its transpose is equal to itself.... does this tell you anything? I guess symmetric But then how can i decompose if matrix A is not given2012-10-27
  • 0
    If $A$ is not given, then you can't do anymore than I said, where $L_{11}$ is the cholesky factor of $A$. Once you know it, then you can extend the factorisation to an additional dimension, as I describe above.2012-10-28
  • 0
    OH, it says that Cholesky decomposition of A is given $A=L*L^T$, but then what does it mean $L_{11}L_{11}=L*L^T$ ?2012-10-28
  • 0
    You have a mistake. In the second matrix, the $(1,1)$ block should be $L_{11}^T$. Also, above, if $L_{11}L_{11}^T=LL^T$, then, $L_{11}=$?2012-10-28
  • 0
    ok thanks, how did i missed that ???2012-10-28
  • 0
    Here is a small problem. I got $L*L_{21}^T=u$. How write an answer for L21^T if L and u are given as it is. I cannot just write the answer as division right???2012-10-28
  • 0
    You (would) need an assumption stating that $A$ is not singular (assumed here), so that the Cholesky decomposition exists. If it does, then $L$ is invertible and this equation becomes $L_{21}^T=L^{-1}u$, which can be calculated once $L$ and $u$ are known.2012-10-28