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

Question

我正在寻找一种用 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 Transactions on Computers，Vol. 11。C-36，第 1 期，第 24-35 页，1987 年 1 月。

定理 2 说

对于具有 s 个节点和拓扑矩阵 A 且rank(A)=s-2 的连通 SDF 图，我们可以找到一个正整数向量 b != 0，使得 Ab = 0，其中 0 是零向量。

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

可能需要求解零空间中的最小正整数向量。为此，请减少 u' 中的每个有理项，使其分子和分母互质。欧几里得算法将适用于此。

Answer 1

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

您可以使用sympy来获得此问题的准确答案。Matrix中的类提供了返回零空间的基向量列表的sympy方法。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])

Answer 2

实际上，这只是基本的线性代数。

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

让我们计算该矩阵的特征值和特征向量。

>>> e = np.linalg.eig(A)
>>> e
(array([ -4.14213562e-01,  -1.05471187e-15,   2.41421356e+00]), array([[-0.26120387, -0.40824829,  0.54691816],
       [-0.36939806, -0.40824829, -0.77345908],
       [-0.89180581, -0.81649658,  0.32037724]]))    
>>>> np.round(e[0], 10)
array([-0.41421356, -0.        ,  2.41421356])

舍入后，我们看到 0 是矩阵 A 的特征值。因此，0-特征值的特征向量 s 是方程组的良好候选者。

>>> s = e[1][:,1]
>>> s
array([-0.40824829, -0.40824829, -0.81649658])    

将特征向量与相关矩阵相乘得到特征向量本身，并按相关特征值缩放。所以，在上面的例子中我们看到：As = 0s = 0

>>> np.round(A.dot(s), 10)
array([ 0.,  0.,  0.])

由于我们对整数解感兴趣，因此我们必须缩放解向量。

>>> x = s / s[1]
>>> x
array([ 1.,  1.,  2.])

希望这个答案能解决您的问题。