2
$\begingroup$

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.

Thanks for your help.

Bin

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.