# 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

## 2 Answers

Estimates can be obtained from Krylov subspace methods, such as GMRES, and PETSc has functionality for that.

For a symmetric matrix, the 2-norm condition number is the spectral condition number, and there exist algorithms to estimate the 2-norm condition number, so if you really do want the condition number for your unpreconditioned matrix, you can use methods for estimating the 2-norm condition number as well. The same methods will work for your preconditioned matrix, although if it is not symmetric, then the 2-norm and spectral condition numbers will not coincide. Note also that condition numbers are norm-dependent, so you should really ascertain the condition number in the norm you're using to assess convergence.

• thanks for your answer. It seems like you want to know the condition number of your operator because you're using an iterative solver, and probably having some issues with convergence. Unfortunately this assumption is not correct. I just want to see the influence of a penalization factor on the condition number of the matrix. I want to learn how high I can choose this factor by looking at how the condition of the matrix changes. – Sebastian Oct 16 '14 at 7:11
• @Sebastian: Next time, please put that information like that in your question when you first post it. – Geoff Oxberry Oct 16 '14 at 18:20

You can get a rough estimation of the condition number using the Gershgorin circle theorem. This article in Wikipedia has a nice explanation: http://en.wikipedia.org/wiki/Gershgorin_circle_theorem

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.

For a SPD matrix the eigenvalues are on the real axis, so you can estimate the highest possible and the lowest possible. Using this you get a rough estimation of the condition number.