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
Répondre
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.
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.
Peut-être LinBox est ce que vous avez besoin.
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
Les meilleures bibliothèques que je connais pour cela sont:
Pari (non GP, mais la bibliothèque du pari lui-même): http://pari.math.u-bordeaux.fr/
NTL (C++): http://www.shoup.net/ntl/
IML: http://www.cs.uwaterloo.ca/~astorjoh/iml.html
Nous commençons à ajouter ce type de fonctionnalité dans flint2 (en particulier dans le module fmpz_mat):
https://github.com/fredrik-johansson/flint2
Le but de silex est le rendre absolument aussi vite que possible, bien que la substance de la matrice est encore fortement en développement.
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. –