# Cholesky decomposition for sparse matrix

I have a symmetric positive definite matrix that is composed of small block diagonal matrices. For example:

$$M = \left[ \begin{array}{ccc} \Sigma & \Psi & \Psi \\ \Psi & \Sigma & \Psi \\ \Psi & \Psi & \Sigma \\ \end{array} \right],$$ where both $$\Sigma$$ and $$\Psi$$ are diagonal matrices.

My question is: Is there an efficient way to perform Cholesky decomposition on this? It is such a regular matrix, that I feel like one must be able to do some trick to simplify the problem, rather than use brute force method.

For 2x2, I found a simple solution shown Block LU decomposition. However, I couldn't figure out how to generalize this to n dimension.

Bin

• I presume it is symmetric positive definite? – copper.hat Jun 16 '12 at 1:05
• Yes, that's correct. Sorry I forgot to mention that. – Bin Jun 17 '12 at 17:41

Suggestion: Try to come up with a general diagonalization method for a matrix of this form. Because both matrices $$\Sigma$$ and $$\Psi$$ are diagonal themselves, you can assume they're scalar for this purpose. For example, using WolframAlpha, we can get a diagonal matrix $$D$$ composed by:
$$D = S^{-1}MS$$
With: $$S = \left[ \begin{array}{ccc} -1 & -1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ \end{array} \right]$$
Then, $$D^{-1}$$ would be straightforward to compute. Note you need to replace the ones with the identity matrix.
As another example, computed with WolframAlpha, for a 4th order $$M$$ matrix, $$S$$ would be:
$$S = \left[ \begin{array}{ccc} -1 & -1 & -1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ \end{array} \right]$$