Cholesky Decomposition

[DavidB]

I will be working with real, symmetric matrices and need to determine if the matrices are positive definite—that’s all. Don’t have to solve the matrix, invert it, calculate its determinant, or anything else at the moment—just determine if it is positive definite. I have done a little investigation, for example, reading on the Mathworld site, which states, “A linear system of equations with a positive definite matrix can be efficiently solved using the so-called Cholesky decomposition.”

Okay . . .
(I am not a mathematics Ph.D., so please be patient with me.)

Two questions:

1) I went on the LAPACK site and tried to find a “Cholesky Decomposition“ using the LAPACK Search Engine. Looked in the “Computational Routines” section, in the “Orthogonal Factorization” and “Symmetric Eigenproblems” sub-sections. I did not find it. Either I am using the wrong terminology, or I am lost. Somebody please let me know what search terms to use. Alternately, if you happen to know exactly which routine to use, please let me know (for real, symmetric matrices).
2) Assuming I find a routine that does the decomposition, is that it? If the decomposition is possible, does that mean the matrix is positive definite, whereas if the routine fails, the matrix is not? Or are additional steps required?

Thanks for any help.


David

[Julie]

Hello,

1. A (real) symmetric matrix has a Cholesky factorization is an equivalent statement as the statement the matrix is (real) symmetric positive definite.
2. In other words, if the Cholesky factorization succeeds then the initial symmetric matrix is positive definite, if the Cholesky factorization fails then the initial matrix is not positive definite.
3. The Cholesky factorization is the recommended way to check whether a given symmetric matrix is positive definite or not. This is faster than any other techniques and this is robust.
4. The LAPACK routine to perform the Cholesky factorization of a double precision matrix is dpotrf (see also spotrf, cpotrf, zpotrf). The routine exits with an INFO parameter. If INFO=0, your matrix is symmetric positive definite, if INFO=i>0, the matrix A(1:i-1,1:i-1) is symmetric positive definite but not the matrix A(1:i,1:i) (and consequently not A).
5. 
   warnings/hints:
   
   1. The lower part of the matrix A (if UPLO='L', the upper part if UPLO='U') is overwritten on exit of _POTRF by the Cholesky factorization
   2. Assuming a user gives you a full matrix A n-by-n, and you want to check if this matrix is symmetric positive definite: do not forget to check the symmetry of A! (before dpotrf). (dpotrf only looks at half of the matrix, this makes sense only if the matrix is symmetric.)
   3. Alternatively, you can also use the packed storage for symmetric matrices to store just half of the matrix (see the PP routines, e.g. dpptrf), however the current routines have slower performance than the full storage (i.e PO routines)

Julie

[DavidB]

Thank-you, Julie.

That was a good explanation.

Sincerely,


David

[rvdg]

Note that if you use the so-called "bordered" variant of Cholesky factorization (or, equivalently, FLAME Cholesky factorization variant 1) you will do the least computation to determine the matrix is NOT SPD. In other words, if you expect the matrix NOT to be SPD, then it is worthwhile to use an algorithmic variant different from the one provided by LAPACK.