# Condition number from incomplete Cholesky factorization

I'm having difficulties patching together from what I read about obtaining the condition number of a real, symmetric, positive definite sparse matrix.

In my code, I found that there is incomplete Cholesky factorization routine (used as preconditioner I suppose). I also have a ILU preconditioner which I could use as Wolfgang Bangerth recommended in an ill-posed version of this question.

I think I can use the Cholesky factorization to estimate the condition number, but I'm not sure.

Result of the preconditioner is $U = L^T$ of my CRS matrix. To estimate the condition number, I need the ratio of maximum and minimum eigenvalues. Using this would be very quick to code.

But how can I use $U$ to get the eigenvalues?

The second best approach I've see so far is writing my matrix to a file and using scipy.sparse.linalg.lsmr to solve the least-squares problems. This also outputs the condition number, but is a little overkill and much more work.

Please understand that matrices and linear algebra are not my daily occupation :)

• I'm confused by your formulas. In general, I don't think the eigenvalues of matrices can be determined by reading off the maximum and minimum of their diagonal elements. That statement is certainly true for diagonal matrices, but not for general symmetric positive definite matrices. Using MATLAB notation, A = [2, 1; 1, 2] is a counterexample; its eigenvalues are 3 and 1. – Geoff Oxberry Oct 15 '14 at 19:01
• I forgot to add where I got this from: google.com/url?q=http://www.maths.manchester.ac.uk/~nstrabic/…. But it's likely that i missunderstood it. I'll try to remove confusion from the question – Sebastian Oct 15 '14 at 19:38
• That reference is about a variant of the QR algorithm that uses Cholesky factorization instead of QR factorization (as in Rutishauser's original LR algorithm). If the matrix is graded, the Cholesky factors can indeed be used to estimate the condition number as Wolfgang Bangerth suggested (see Roy Mathias, Fast Accurate Eigenvalue Computations Using The Cholesky Factorization). I'm not sure the same holds true for the incomplete Cholesky factor. – Christian Clason Oct 15 '14 at 20:15
• It would probably be helpful if you also mentioned what precisely you need the condition number for. – Christian Clason Oct 15 '14 at 20:21
• @ChristianClason I'm working with FE method, which penalizes jumps on a non-conforming interface. There is a penalty factor involved, and I'd like to measure how varying the penalty factor changes the condition of the matrix (specifically: how high can I choose the penalty factor). – Sebastian Oct 16 '14 at 6:55

For a complex matrix $A$ of size $n\times n$, its n Gershgorin circles are drawn in the complex plane, the center of the circles are $a_{ii}$, the radius of the ith circle is $\sum_{i\neq j} |a_{ij}|$. The theorem says that every eigenvalue of $A$ lies inside a Gershgorin circle.