Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The Cholesky factorization is the classic test to check if a matrix is positive definite. In infinite precision it is also an exact test: A matrix has a Cholesky factorization iff it is positive definite. However, in floating point arithmetic the Cholesky test is not perfect and two types of errors can (probably) be made:

  1. A false positive error: The Cholesky test passes when the matrix is indefinite.

  2. A false negative error: The Cholesky test fails when the matrix is positive definite.

The conditions for false negative errors is pretty well understood. For example, if a matrix $A$ is positive definite then defining $D = \hbox{diag}(A)^{1/2}$ and $A = DHD$, a false negative error is made if $\lambda_{\min}(H) \leq -n \gamma_{n+1}/(1-\gamma_{n+1})$, $\gamma_{n} = \mathcal{O}(n u)$ with $u$ being unit round off.

This is a satisfactory result because it can also be shown that the test makes no error on positive definite matrices if $\lambda_{\min}(H) > n \gamma_{n+1}/(1-\gamma_{n+1})$. For more details see theorem 10.7, page 200 of Accuracy and Stability of Numerical Algorithms By Nicholas J. Higham.

The situation seems more difficult for quantifying false positive error. On indefinite matrices the Cholesky factorization is numerically unstable so one would expect examples where an indefinite matrix (which is far from positive definite) still passes the Cholesky test. Does anyone know of an example? Can the Cholesky factorization be used in finite precision as a test without quantifying the false positive error? Is it just a highly improbable event that an indefinite matrix causes a false positive error?

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.