Module d'algèbre linéaire sur les entiers

J'ai récemment rencontré le problème suivant. Étant donné une liste de vecteurs (ici je veux dire tuple) tous avec des entrées entières, y at-il un paquet (la langue n'est pas trop un problème, le plus vite le mieux, donc je suppose C) pour déterminer très rapidement quand un autre vecteur entier est la durée de la liste d'origine? J'ai besoin de faire cette arithmétique sur les entiers (pas de division). Je suis sûr qu'il y en a un, mais je voulais contourner la longue revue de la littérature.Module d'algèbre linéaire sur les entiers

Source

2010-11-12 Lance Miller

Est-ce que LINPACK a quelque chose?

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

Nous avons utilisé l'utiliser beaucoup dans mes jours vecteur/supercalculateur, et il y a généralement des versions spécifiques du matériel.

Source

2010-11-12 00:31:30 winwaed

Le problème est que j'ai besoin de cela pour utiliser uniquement l'arithmétique intégrale non rationnelle. Je ne suis pas sûr que LINPACK puisse garantir que l'équation d'appartenance n'a que des coefficients entiers. –

@Lance: Il ne peut pas. –

@Stev Merci d'avoir vérifié cette hypothèse. –

Vous pouvez utiliser la fonction mathnf dans PARI pour calculer le Hermite normal form de la matrice contenant vos vecteurs spanning comme des colonnes. Les colonnes de la matrice HNF couvrent le même treillis, et il est trivial de vérifier si un vecteur est dans ce treillis. Il y a beaucoup plus de bibliothèques capables de calculer le HNF - Google est votre ami.

Source

2010-11-12 01:09:43

Peut-être LinBox est ce que vous avez besoin.

Source

2010-11-25 19:22:02 jmbr

CVXOPT peut être une option. En particulier, regardez cette fonction:

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

Regardez ce billet: binary linear programming solver in Python

Source

2010-11-25 19:59:57 Alejandro