How do you find the Cholesky decomposition of the sum of two positive definite matrices without adding the matrices directly? If you're given two positive definite matrices ($A_1,A_2$) and the Cholesky Decomposition of those two matrices ($L_1,L_2$ such that $A_1=L_1L_1^T, A_2=L_2L_2^T$). Is there a way to find the Cholesky decomposition of $A_1+A_2$ without adding the two matrices directly? i.e. $A_1+A_2 = f(L_1,L_2)f(L_1,L_2)^T$.
 A: No. This question and easier variants get asked regularly on [scicomp.se], and the answer is invariably no. See for instance https://scicomp.stackexchange.com/q/10630/4405 .
TL;DR:

*

*low rank update (e.g., one column added, one element changed...): factorizations can be efficiently updated.

*low norm update: you can approximate the inverse using perturbative approaches, or use the pre-update matrix as a preconditioner in an iterative method.

*full-rank update (e.g., a diagonal matrix is added): no known solutions apart from recomputing the factorization.

A: Yes. More generally, for $X \in \mathbb{C}^{m_1 \times n}$, $Y \in \mathbb{C}^{m_2 \times n}$, you can compute the QR decomposition
$$ \begin{bmatrix} X \\ Y \end{bmatrix} = QR . $$
Then, since
$$ X^* X + Y^* Y = \begin{bmatrix} X \\ Y \end{bmatrix}^* \begin{bmatrix} X \\ Y \end{bmatrix} = (QR)^*(QR) = R^* R, $$
it follows that a Cholesky factorization of $X^* X + Y^* Y$ is $R^* R$. This method of computing $R$ will generally be far more accurate than the "direct" method of first computing the sum and then factorizing, essentially because forming $X^*X$ and $Y^*Y$ squares the condition numbers of $X$ and $Y$. Also note that the QR method gracefully handles the rank deficient case, e.g., when $m_1 + m_2 < n$, whereas the direct method may very likely fail.
On the other hand, the work of both methods is comparable in the general case. For real matrices, we can estimate $\sim 2(m_1+m_2)n^2 - \tfrac{2}{3}n^3$ flops for Householder orthogonalization versus  $\sim (m_1 + m_2) n^2 + \tfrac{1}{3}n^3$ for the direct method (if we exploit the symmetry in the matrix multiplication). In special cases, the work of the QR decomposition can be reduced. For example, when $X$ is triangular and $Y$ is a single row, the QR decomposition can be computed with $n$ Givens rotations in $O(n^2)$ work. This is exactly the classic rank-1 Cholesky update procedure. It is likely some reduction is possible in the case $X$ and $Y$ are both triangular as in the question, but the flop count will still be $O(n^3)$.
