Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi all,

Let $\mathbf{A} \in \mathbb{Z}^{M \times N}$. Suppose that $\mathbf{A} \cdot \vec{x} = \vec{0}$, where $\vec{x} \in \mathbb{N}^{N \times 1}$. Does anyone know about a C/C++/Java program that can compute the null-space basis vector(s) exactly?

share|improve this question
    
This is not the right site to ask this particular question, I think. In the FAQ you will find some suggestions. (If you really want $\vec x$ to be in $\mathbb N^{N\times 1}$, then the solution set is not a vector space, and finding a "basis" for whatever it is is a bit more complicated...) –  Mariano Suárez-Alvarez Oct 18 '10 at 14:05
2  
Your best bet is to find the rational null-space (treat A as a rational matrix) and then intersect that null-space with $\mathbb{N}^N$. –  Alex B. Oct 18 '10 at 14:08
    
If you use MATLAB the 'r' option for the 'null' command will be of use. –  Steve Huntsman Oct 18 '10 at 14:40
    
Pari/GP will do that. –  Felipe Voloch Oct 18 '10 at 15:02
1  
The best solution, Imho, is to use linbox. This is a c++ library designed for exact linear algebra over Q, its finite extensions and finite fields. –  Andy B Mar 5 '11 at 3:37
show 6 more comments

3 Answers

The question seems to be about programs that can compute the nullspace of an integer matrix exactly. (Though there seems to be the constraint that all the entries in the solution vector are positive, which I'm going to ignore.) The best software you might want to use could depend on the size of your matrices, which is a function of: (1) the parameters $M$, $N$, (2) the number of bits of the entries, and (3) the sparseness of the matrix.

  • IML (Integer Matrix Library) -- this is a free C library, but what it does is compute the rational kernel of a system defined over the integers, so it isn't directly useful for your problem. Anyway, in my benchmarks, this is the fastest library available for computing the rational kernel if your matrix is large (both $M$ and $N$), dense, and the entries are also large. When entry sizes get to several hundred bits or larger, IML seemed to me in 2007 to be by far the fastest library in existence (easily beating Mathematica, Magma, NTL, etc.). IML is used part of Sage and used for the kernel function. Getting going with IML standalone can be hard (though I contributed code a few years ago to make it easier), but if you just want a library to link into an existing C program, you'll definitely want to look into IML.

  • PARI -- this free calculator (which is also usable as a C library) is extremely good for computing kernels of small matrices, e.g., when the entries aren't too big and the number of rows and columns aren't too large either (say, less than 100). It's optimized for this small case, since that's what comes up in class group computations, among other things. The command to use is matkerint, e.g., "matkerint([1,2,3;4,5,6;7,8,9])".

  • SAGE -- this free software uses some combination of IML, PARI, Linbox, NTL and a bunch of new code to compute kernels of integers matrices. In some cases (e.g., nearly square matrices) it is very good, and it could be good in far more cases but I got lazy and didn't implement fast algorithms for all shapes of matrices. Type "A = matrix(ZZ,3,3,[1..9])" to make an example integer matrix; then "A.kernel()" will find the kernel over ZZ (by default, contrary to what another answer on this page claims). If you type "A._k[press tab key]" you'll see that you can directly call two other routines for computing kernels, one involving PARI, and the other a $p$-adic algorithm. Behind the scenes, really the Hermite normal form of the matrix is being computed using the algorithm described here. The HNF algorithm in Sage makes fundamental use of IML in several ways behind the scenes.

  • Magma -- non-free and closed source, but has a fast tuned Hermite normal form algorithm presumably similar to the one in Sage, which for certain (not all) ranges of inputs is the best available.

  • Mathematica -- in my benchmarks (from 2007), as the matrices get very big this gets totally useless compared to Magma or Sage, but it is fine for small matrices. Similar remarks apply about Maple, at least as of 2007.

Here's a potentially helpful example in Sage, which illustrates some of the computations discussed here and elsewhere, and explains how to work with some matrices and modules in Sage:

sage: A = random_matrix(ZZ,5,2); B = random_matrix(ZZ,5,2)
sage: A.kernel()
Free module of degree 5 and rank 3 over Integer Ring
Echelon basis matrix:
[ 1 60  0  1 30]
[ 0 66  0  1 33]
[ 0  0  1  0  0]
sage: A.kernel().intersection(B.kernel())
Free module of degree 5 and rank 1 over Integer Ring
Echelon basis matrix:
[  19 -378  -93   -4 -189]
sage: VA = A.change_ring(QQ).kernel(); VB = B.change_ring(QQ).kernel()
sage: W = VA.intersection(VB); W
Vector space of degree 5 and dimension 1 over Rational Field
Basis matrix:
[      1 -378/19  -93/19   -4/19 -189/19]
sage: W.intersection(ZZ^5)
Free module of degree 5 and rank 1 over Integer Ring
Echelon basis matrix:
[  19 -378  -93   -4 -189]
share|improve this answer
add comment

The magic words are "Smith normal form"

share|improve this answer
    
See also the comments thread. –  Alex B. Mar 5 '11 at 4:55
add comment

I would recommend using NTL (Number Theory Library). Its LLL algorithm allows you to compute the kernel of a matrix over the integers, moreover the basis found is usually "short" (in the sense that the length of the basis vectors are short).

share|improve this answer
add comment

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.