views:

506

answers:

4

I have a program that uses JAMA and need to test is a matrix can be inverted. I know that I can just try it and catch an exception but that seems like a bad idea (having a catch block as part of the "normal" code path seems to be bad form).

A test that also returns the inverse (or run in a better O() than the inverse operation) would be preferred.

+2  A: 

In general, if you can't solve the matrix, it's singluar (non-invertable). I believe the way that JAMA does this is to try to solve the matrix using LU factorization, and if it fails, it returns "true" for isSingular().

There isn't really a general way to just look at the elements of a matrix and determine if it is singular - you need to check each column to see if it is orthogonal with the others (i.e. the nullspace for the matrix is 0). LU factorization is quite fast, usually... there are times where it takes the bulk of an operation, however.

Do you have an actual speed problem you're trying to overcome?

codekaizen
It's not perf. I just don't want to have code that will always throw (it would be the loop exit)
BCS
I'm not seeing a isSingular
BCS
You're right, my memory was bad. You get the LU decomposition and then check isNonsingular: http://math.nist.gov/javanumerics/jama/doc/Jama/LUDecomposition.html#isNonsingular()
codekaizen
A: 

For a square matrix, you could you just check its determinant --- Matrix.det() returns zero if and only if the matrix is singular. Of course, you will need to watch out for ill-conditioned matrices too.

Zach Scrivena
IIRC in general O() for det is exp(n), inv is n^3. Ouch
BCS
Guess we need to see how it's actually being implemented. Some approaches can do better than n! --- we can get n^3 using LU/Cholesky/QR decomposition as you suggest.
Zach Scrivena
A: 

If an exception is thrown, what is your recovery position?

If you do an LU decomposition and find that it's singular, do you catch the exception and try an SVD (singular value decomposition) instead?

duffymo
In that cases I terminate. I'm trying to catch a (common) corner cases that happens to have a trivial solution that doesn't need the inverse.
BCS
A: 

sounds like you would like to estimate the reciprocal of the condition number.

This site looks somewhat promising...

See also Golub and Van Loan, p. 128-130. (If you don't have a copy of it, get one.)

...or Higham, who's an authority on numerical methods. Except that it's kind of hard to parse the math... like walking through a thicket of raspberry bushes. :/

Or maybe check the Octave sources for their version of MATLAB's rcond(). I found this post.

Jason S
The condition number is only an indicator of fitness for numerical computation on a machine with limited precision - it won't give you insight into whether the matrix itself is singular.
codekaizen
I'm amused at your use of the word "only". Singular is an extreme case of high condition number. If a matrix can be inverted but it has a high condition number then you are teetering on the edge of invertibility.
Jason S
Sure. But this doesn't really answer the poster's question.
codekaizen