Detecting singular system during Cholesky resolution I am solving small linear systems with a symmetric positive matrix by the method of Cholesky, without pivoting.
"Bad" matrices are detected when you take the square root of a diagonal element, which must be strictly positive. But I don't think this solves the case of some near-singular systems for which the final answer can be a nonsense.
Is there a better numerical criterion to detect rank-deficiencies ? (With a computational complexity no exceeding Cholesky.)
 A: The criterion for a bad symmetric $>0$ matrix $A$, concerning the Choleski method, is the same as for the LU decomposition. Just calculate the condition number of $A$; let $cond(A)=\dfrac{\lambda_1}{\lambda_n}\approx 10^k$ where $\lambda_1\geq\cdots\geq \lambda_n$ are the $>0$ eigenvalues of $A$. It suffices to calculate approximations of $\lambda_1,\lambda_n$ by the power method and the inverse power method. Unfortunately, if $k$ is great, then, in general, $\lambda_n$ has order of magnitude $10^{-k}$ and we need many iterations of the inverse power method. 
EDIT 1. Anyway, we can have an estimation of $\lambda_n$, for great $n$, in $4/3n^3$ -and not in $o(n^3)$ as I wrote few moment ago-. On the other hand, $||A^{-1}||$ can be estimated, using an iterative algorithm, with $O(n^2)$ complexity; in fact this estimate can be $10$ times lower than the value itself. Nevertheless even such a precision is sufficient; indeed, it suffices to add a significant digit during the calculation (see below).
Consider an equation $Ax=b$, with $b$ a random vector; then $b$ has non-zero components on the eigenvectors associated to $\lambda_1,\lambda_n$ and we are in a worst case -the relative error $\dfrac{||\Delta x||}{||x||}$ is maximal- Thus if you work with $t$ significant digits, then you obtain $x$ with $t-k$ significant digits.
Finally the simplest method is as follows. Step 1. You calculate (using $t$ significant digits) $x$. Step 2. You calculate $\dfrac{||Ax-b||}{||b||}\approx 10^r$. Step 3. If you want $s$ significant digits for $x$, then you recalculate $x$ (using $t+r+s$ significant digits). (of course $s$ can be $<0$).
Remark. If there is a break in Step 1., then you must before calculate $cond(A)$.
EDIT 2. I speak above, about an estimate of $cond(A)$, that should be  calculable in $O(n^2)$; in fact, it needs the knowledge of the Cholesky decomposition; finally, it seems that we cannot know an estimate of $cond(A)$ before the end of the decomposition. As you write in your comment, we can try to test the eventually positive elements $c_{ii}$ when they appear on the diagonal of the matrix $C$ s.t. $CC^T=A$. Unfortunately, the choice of a convenient $\epsilon$ is not easy as we can see on the following example:
Let $H=[\dfrac{1}{i+j-1}]$ be the Hilbert matrix of dimension $20$ and $K=[\dfrac{1}{2n-i-j+1}]\in M_{20}$ where $n=20$. Clearly $H,K$ has same $cond_2=t\approx 2.5\times 10^{28}$. One has $H=CC^T,K=DD^T$ where $C,D$ have same $cond_2=\sqrt{t}\approx 1.6\times 10^{14}$. Yet, $\inf(spectrum(C))\approx 4.5\times 10^{-12}$ is very different from $\inf(spectrum(D))\approx 1.1\times 10^{-8}$. The last but not the least, the small values of the $C_{ii}$ appear during the second part of the algorithm; then, even if you find a good test, the complexity is widely in $O(n^3)$.
