optimization - 整数上的线性代数包

Question

我最近遇到了以下问题。给定一个包含整数条目的向量列表（这里我的意思是元组），是否有一个包（语言不是太大的问题，越快越好，所以我猜是 C）可以非常快速地确定另一个整数向量何时在原始列表的跨度？我需要对整数进行此算术运算（无除法）。我敢肯定有一个，但想绕过冗长的文献回顾。

Answer 1

CVXOPT可能是一种选择。特别是看这个函数：

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

另请看这篇文章：Python 中的二进制线性规划求解器

Answer 2

您可以使用PARImathnf中的函数来计算包含作为列的跨越向量的矩阵的Hermite 范式。HNF 矩阵的列跨越相同的格，检查向量是否在该格中是很简单的。还有更多的库能够计算 HNF——谷歌是你的朋友。

Answer 3

也许LinBox是您所需要的。

Answer 4

LINPACK有什么吗？

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

在我的矢量/超级计算机时代，我们经常使用它，并且通常有特定于硬件的版本。

Answer 5

我所知道的最好的图书馆是：

Pari（不是 GP，而是 Pari 库本身）： http: //pari.math.u-bordeaux.fr/

NTL（C++）：http ://www.shoup.net/ntl/

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

我们开始在 flint2 中添加这种功能（特别是在 fmpz_mat 模块中）：

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

燧石的目的是让它尽可能快，尽管矩阵的东西仍在大量开发中。