Cholesky Factorization with submatrices

Question

Let $\mathbf{A}\in\mathbb{R}^{N \times N}$ be symmetric positive definite. For some $1\leq k<N$, partition $$\mathbf{A}=\begin{pmatrix}\mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{12}^T & \mathbf{A}_{22}\end{pmatrix},$$ where $\mathbf{A}_{11}$ is $k\times k$ and $\mathbf{A}_{22}$ is $(N-k)\times (N-k)$.

Let $\mathbf{A}=\mathbf{L}\mathbf{L}^T$ be a Cholesky factorization, where $$\mathbf{L}=\begin{pmatrix}\mathbf{L}_{11} & \mathbf{0} \\ \mathbf{L}_{21} & \mathbf{L}_{22}\end{pmatrix}.$$ The $k\times k$ matrix $\mathbf{L}_{11}$ and the $(N-k)\times (N-k)$ matrix $\mathbf{L}_{22}$ are lower triangular.

Express the submatrices $\mathbf{L}_{ij}$ in terms of the submatrices $\mathbf{A}_{ij}$ and appropriate Cholesky factors.

I've been able to find that,

$$\mathbf{A}_{11} = \mathbf{L}_{11}\mathbf{L}_{11}^T$$ $$\mathbf{A}_{12} = \mathbf{L}_{11}\mathbf{L}_{21}^T$$ $$\mathbf{A}_{12}^T = \mathbf{L}_{21}\mathbf{L}_{11}^T$$ $$\mathbf{A}_{22} = \mathbf{L}_{21}\mathbf{L}_{21}^T + \mathbf{L}_{22}\mathbf{L}_{22}^T,$$

but I am unsure of how to solve for the $\mathbf{L}_{ij}$'s.

Does anyone have any ideas?

Answer 1

1. Equation (1) gives $L_{11} = A_{11}^{1/2}$. To compute the square root, calculate eigenvalue decomposition, i.e., $A_{11} = Q\Lambda Q^\top$, then $A_{11}^{1/2} = Q\Lambda^{1/2}Q^\top$.
2. Equation (2) gives $L_{21} = A_{11}^{-1/2}A_{12}^\top$.
3. Equation (4) gives $L_{22} = \left(A_{22} - A_{11}^{-1/2}A_{12}^{\top}A_{12}A_{11}^{-1/2}\right)^{1/2}$. The square root can be computed similar to step 1.

Answer 2

• $A_{11}=L_{11}L_{11}^T$ implies that $L_{11}$ is the Cholesky factor of $A_{11}$. Hence, compute it by using the Cholesky factorization on the submatrix $A_{11}$.
• From $A_{12}^T=L_{21}L_{11}^T$, $L_{21}=A_{12}^TL_{11}^{-T}=(L_{11}^{-1}A_{12})^T$. That is, compute the forward substitution with $L_{11}$ and multiple right-hand sides consisting of the columns of $A_{12}$ and transpose the result to get $L_{21}$.
• In $A_{22}=L_{21}L_{21}^T+L_{22}L_{22}^T$, we know already $L_{21}$ (and of course $A_{22}$), so $L_{22}$ is given by the Cholesky factorization of $A_{22}-L_{21}L_{21}^T$.