1
$\begingroup$

A similar question is asked here, but for LU decomposition instead of Cholesky, which makes this less trivial. I am using an algorithm (in Matlab) that spends a lot of time computing the Cholesky factor $C$ of an upper triangular matrix $R$. The diagonal of $R$ is composed of ones only, and a lot of its values are near zero, in case that's relevant.

I have observed that each row of the matrix $C$ is a scalar multiple of the same row in $R$, and many rows are unaltered (apart from what I think are floating point variations, i.e., in the order of $10^{-10}$). I suspect that this is an easy result to obtain but I am unable to prove it.

What I would really like, however, is to have a way to compute those scalars that would be faster than performing the Cholesky decomposition, as that might speed up my code significantly.

EDIT: I have also observed that those factors are the eigenvalues of $C$, which is a trivial consequence of this and the fact that the diagonal of $R$ is composed of ones.

EDIT2: As I've said in the comments, the Matlab function chol that I'm using is only using the upper triangular entries of the input matrix, so I am not in fact calculating the Cholesky factorization of an upper triangular matrix, but of a symmetric positive semi-definite matrix. However, I still don't know why the rows of $C$ are multiples of the rows of (the upper triangular part of) $R$.

$\endgroup$

1 Answer 1

2
$\begingroup$

You have a Cholesky decomposition for symmetric, positive definite matrices... In order for your matrix to be upper triangular and symmetric, it must in fact be diagonal. Regarding your observation about the relation between the rows in the original matrix and the lines/rows in decomposition, consider this example: $$ A = \left( \begin{array}{cccc} 1 & 0.2 & 0 & 0 \\ 0.2 & 1 & 0.2 & 0 \\ 0 & 0.2 & 1 & 0.2 \\ 0 & 0 & 0.2 & 1 \\ \end{array} \right), \qquad L = \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0.2 & 0.979796 & 0 & 0 \\ 0 & 0.204124 & 0.978945 & 0 \\ 0 & 0. & 0.204302 & 0.978908 \\ \end{array} \right) $$

Although it is true that $A = L L^T$, there is no such relation.

$\endgroup$
6
  • $\begingroup$ Ah, that's right. Indeed an upper triangular matrix is passed to Matlab's "chol" function, but I failed to notice this, in the documentation of the function: "R = chol(A) factorizes symmetric positive definite matrix A into an upper triangular R that satisfies A = R'*R. If A is nonsymmetric , then chol treats the matrix as symmetric and uses only the diagonal and upper triangle of A." But can you still explain why the rows of C are multiples of rows of R? $\endgroup$ Jul 23, 2021 at 13:46
  • 1
    $\begingroup$ I don't think they are, in general. Why don't you try with some small example? $\endgroup$ Jul 23, 2021 at 14:03
  • $\begingroup$ Thanks for the update. Indeed I have noticed that the values away from the diagonal tend to go to zero, although the first 4 diagonals still have values near 1. Also, this example is a 4000X4000 matrix. When I tried a smaller 100X100 random matrix, I did not get that behaviour I mentioned. However, if I use a 100X100 matrix with the same effect on the diagonals, I get that behaviour back. Maybe there's some asymptotic behaviour that can be exploited? $\endgroup$ Jul 23, 2021 at 14:33
  • $\begingroup$ An update: I'm not being able to replicate this behaviour with random generated positive semidefinite matrices with only a few diagonals non-zero. Even if only the second diagonal is nozero, I don't get this behaviour, it's probably something specific to the matrix R in question. I will update with how that matrix is constructed in a few minutes. $\endgroup$ Jul 23, 2021 at 14:51
  • $\begingroup$ It seems the matrix R is mostly a block diagonal, with 9X9 blocks that are symmetric positive semidefinite. Other nonzero values exist outside of this block diagonal however, but they're a clear minority. This is probably related. $\endgroup$ Jul 23, 2021 at 15:11

You must log in to answer this question.

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