Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

I have a simple (and small) linear homogeneous system $Ax=0$, where the entries of the $N\times M$ matrix $A$ are small integers. I do not need fancy methods which efficiently solve almost singular matrices and treat roundoff errors etc. But I need to know if a system is singular and also the general solution for underdetermined systems. It must be rock-solid. Any reference to such an algorithm is welcome. I am coding in C. Is SVD the way to go?

share|improve this question
    
Are you looking for integer solutions as well? What is the size of $N$ and $M$? By "general solution", do you mean a basis of the null space of $A$? –  Christian Clason Jan 4 '13 at 22:30
    
Yes, essentially I mean a basis of the null space. Size of N and M can vary, where N>M and M>N is both possible . Typical size could be N,M\sim 10. I searched a bit further and found that 'reduced Row Echelon form' could be the solution. Since A has integer elements only rationals would appear and I could compute exact results. Anybody aware of an open implementation (any language). –  highsciguy Jan 4 '13 at 22:38
    
I.e. I search an implementation of the Gaussian elemination for NxM matrices. I know that of Numerical recipies, but it is for NxN. I understand now that SVD would work. But it seems a bit overkill to me with the additional advantage that it would use floats and probably be to long to adopt it to integers/rationals. –  highsciguy Jan 4 '13 at 23:00

3 Answers 3

up vote 3 down vote accepted

The Integer Matrix Library is a C library that claims to be able to compute the null space of an integer matrix. See also this answer on MathOverflow to the exact same question, which gives a list of libraries (including PARI, which also can be called from C and is still being updated). You could also take a look at LinBox, even though it's written in C++.

share|improve this answer
1  
The reference to IML was pretty useful to me. It does what I want. Also the question on MathOverflow is really the same. –  highsciguy Jan 6 '13 at 15:06

The general solution of your underdetermined system is that $x$ is a member of the nullspace of $A$.

To find the nullspace of $A$, the most numerically stable method is to use an SVD. See Null-space of a rectangular dense matrix for further details.

share|improve this answer

The SVD will both (1) tell you what the null space of your matrix is (2) give you the pseudo-inverse of the matrix in the event that it is singular. The SVD is, generally speaking, a very handy matrix factorization and for your stated purposes should definitely get the job done.

If you're determined to write the code yourself, Trefethen and Bau's book has enough details to work from, either implementing the really bad way of finding the eigendecomposition of A*A or the proper way using bidiagonalization.

However, if you just happen to be working in C and don't feel the need to do it yourself, the Wikipedia page for the SVD has a long list of libraries that will implement it for you, chief among which is the GNU Scientific Library. Or, a google search of "SVD c source code" turns up a couple results as well.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.