python之在 Python 中求解线性整数方程组

我正在寻找一种在 Python 中求解线性方程组的方法。 特别是，我正在寻找大于所有零的最小整数向量并求解给定方程。 例如，我有以下等式:

想解决 .

在这种情况下，求解该方程的最小整数向量是 .

但是，我怎样才能自动确定这个解决方案呢？ 如果我使用 scipy.optimize.nnls，比如

A = np.array([[1,-1,0],[0,2,-1],[2,0,-1]]) 
b = np.array([0,0,0]) 
nnls(A,b) 

结果是 (array([ 0., 0., 0.]), 0.0)。 这也是正确的，但不是所需的解决方案...

编辑:对于某些方面的不精确，我深表歉意。 如果有人对细节感兴趣，问题来自论文 “数字信号处理同步数据流程序的静态调度”，Edward A. Lee 和 David G. Messerschmitt， IEEE 计算机交易，卷。 C-36，第 1 期，第 24-35 页，1987 年 1 月。

定理 2 说

For a connected SDF graph with s nodes and topology matrix A and with rank(A)=s-2, we can find a positive integer vector b != 0 such that Ab = 0 where 0 is the zero vector.

在定理 2 的证明之后，他们说

It may be desirable to solve for the smallest positive integer vector in the nullspace. To do this, reduce each rational entry in u' so that its numerator and denominator are relatively prime. Euclid's algorithm will work for this.

请您参考如下方法:

要找到您想要的确切解决方案，numpy 和 scipy 可能不是最好的工具。他们的算法通常以 float 工作，并且不能保证给出准确的答案。

您可以使用 sympy得到这个问题的确切答案。 sympy 中的 Matrix 类提供了方法 nullspace() 返回零空间的基向量列表。这是一个例子:

In [20]: from sympy import Matrix, lcm 
 
In [21]: A = Matrix([[1, -1, 0], [0, 2, -1], [2, 0, -1]]) 

获取零空间中的向量。 nullspace() 返回一个列表；此代码假定 A 的秩为 2，因此列表的长度为 1:

In [22]: v = A.nullspace()[0] 
 
In [23]: v 
Out[23]:  
Matrix([ 
[1/2], 
[1/2], 
[  1]]) 

找到 v 中值的分母的最小公倍数，以便我们可以将结果缩放到最小整数:

In [24]: m = lcm([val.q for val in v]) 
 
In [25]: m 
Out[25]: 2 

x 保存整数答案:

In [26]: x = m*v 
 
In [27]: x 
Out[27]:  
Matrix([ 
[1], 
[1], 
[2]]) 

要将该结果转换为 numpy 整数数组，您可以执行以下操作:

In [52]: np.array([int(val) for val in x]) 
Out[52]: array([1, 1, 2])