Linear algebra package over the integers

Question

I've recently ran into the following problem. Given a list of vectors (here I mean tuple) all with integer entries, is there a package (language isn't too much an issue, the faster the better, so I guess C) to very quickly determine when another integer vector is in the span of the original list? I need to do this arithmetic over the integers (no division). I'm sure there is one, but wanted to circumvent the lengthy literature review.

score 2 · Answer 1 · answered Nov 12 '10 at 01:09

You could use the mathnf function in PARI to compute the Hermite normal form of the matrix containing your spanning vectors as columns. The columns of the HNF matrix span the same lattice, and it is trivial to check if a vector is in this lattice. There are many more libraries able to calculate the HNF -- Google is your friend.

score 2 · Answer 2 · edited May 23 '17 at 10:26

CVXOPT may be an option. In particular, look at this function:

cvxopt.glpk.ilp = ilp(...)  
Solves a mixed integer linear program using GLPK.

(status, x) = ilp(c, G, h, A, b, I, B)

PURPOSE
Solves the mixed integer linear programming problem

minimize    c'*x
subject to  G*x <= h
            A*x = b
            x[I] are all integer
            x[B] are all binary

Look at this post also: binary linear programming solver in Python

score 1 · Answer 3 · answered Nov 25 '10 at 19:22

1

Perhaps LinBox is what you need.

answered Nov 25 '10 at 19:22

jmbr

3,298
23
23

score 0 · Answer 4 · answered Nov 12 '10 at 00:31

0

Does LINPACK have anything?

http://en.wikipedia.org/wiki/LINPACK

We used to use it a lot in my vector/supercomputer days, and there are usually hardware specific versions.

answered Nov 12 '10 at 00:31

winwaed

7,645
6
36
81

The issue is that I need this to use only integral arithmetic not rational. I'm not sure that LINPACK can guarantee that the equation for membership only has integer coefficients. – Lance Miller Nov 12 '10 at 00:38
@Stev Thanks for verifying that assumption. – Lance Miller Nov 12 '10 at 01:06

score 0 · Answer 5 · answered Jan 05 '11 at 16:41

The best libraries I know of for this are:

Pari (not GP, but the Pari library itself): http://pari.math.u-bordeaux.fr/

NTL (C++): http://www.shoup.net/ntl/

IML: http://www.cs.uwaterloo.ca/~astorjoh/iml.html

We are starting to add this sort of functionality in flint2 (in particular in the fmpz_mat module):

https://github.com/fredrik-johansson/flint2

The aim of flint is make it absolutely as fast as possible, though the matrix stuff is still heavily under development.

Linear algebra package over the integers

5 Answers5