2
$\begingroup$

Suppose I have a large $n\times{}n$ matrix with $n>1000$ say. I would like to find the quickest way to check if it is positive definite. My matrices are sparse so at the moment I am using sparse matrices in Matlab and the command 'chol'. Is there a quicker way (preferably in Matlab)? Thanks!

My matrices are banded, if that helps.

$\endgroup$
  • $\begingroup$ Check that all eigenvalues are positive. If the matrix is real, it is even simpler; see en.wikipedia.org/wiki/… $\endgroup$ – parsiad Jun 26 '16 at 14:57
  • 1
    $\begingroup$ That's slower than Cholesky factorization, I'm not bothered about eigenvalues, just the quickest way to see if it's positive definite. $\endgroup$ – Mathmo Jun 26 '16 at 15:04
  • 1
    $\begingroup$ You can check the quadratic form on, say, the standard basis in cubic time. And you can do it in parallel. Is that adequate? I'm not sure how much better you can do without some restrictions on the matrix you're talking about. $\endgroup$ – Ian Jun 26 '16 at 15:15
  • $\begingroup$ @Mathmo: did you see the comment on Wikipedia about using Descartes rule of signs when the matrix is real? $\endgroup$ – parsiad Jun 26 '16 at 15:44
  • $\begingroup$ Computational Science StackExchange might be a better venue for this question. $\endgroup$ – horchler Jun 26 '16 at 15:50
2
$\begingroup$

In general computing the Cholesky factorization of a symmetric matrix A is the fastest method to check if A is positive definite.

For banded matrices there is a specialized algorithm of computing the Cholesky factorization, which is faster than the Cholesky factorization of a sparse matrix. Such algorithm is not available in Matlab.

Symmetric positive definite matrices have positive elements on the main diagonal.

You may also apply the Gershgorin circle theorem to find constraints on eigenvalues of A. If this theorem shows that all eigenvalues are positive, then it proves, that the matrix A is positive definite.

The last two methods are very fast and can be used as fast checks, but do not work in general.

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