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