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$
2
  • $\begingroup$ I presume it is symmetric positive definite? $\endgroup$
    – copper.hat
    Jun 16, 2012 at 1:05
  • $\begingroup$ Yes, that's correct. Sorry I forgot to mention that. $\endgroup$
    – Bin
    Jun 17, 2012 at 17:41

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .