1

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

Rodrigo de Azevedo
  • 1
Sirplentifus
  • 125

1 Answers1

2

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.

PierreCarre
  • 20,974
  • 1
  • 18
  • 34
  • 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?

     – Sirplentifus Jul 23 '21 at 13:46
  • 1
    I don't think they are, in general. Why don't you try with some small example? – PierreCarre Jul 23 '21 at 14:03
  • 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? – Sirplentifus Jul 23 '21 at 14:33
  • 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. – Sirplentifus Jul 23 '21 at 14:51
  • 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. – Sirplentifus Jul 23 '21 at 15:11
  • Ok, so with some more inspection, I noticed that in each of those blocks, the diagonals are constant valued. Furthermore, the cholesky factor of a block diagonal matrix will be a block diagonal matrix of the cholesky factors of the blocks in the original matrix. Together, these things explain what I was observing. Thank you for the explanation, and sorry that I didn't give enough information. – Sirplentifus Jul 23 '21 at 15:24