用numpy求整数整数线性系统

Question

我正试图用numpy来解决一个超定的线性方程组。目前，我正在做这样的事情（作为一个简单的例子）：

a = np.array([[1,0], [0,1], [-1,1]])
b = np.array([1,1,0])

print np.linalg.lstsq(a,b)[0]

[ 1.  1.]

这有效，但使用浮点数。有没有办法只用整数解决系统？我尝试了一些方法

print map(int, np.linalg.lstsq(a,b)[0])

[0, 1]

为了将解决方案转换为一组int，期待[1, 1]，但显然我错过了一些东西。有人能指出我正确的方向吗？

Answer 1

你正在寻找一个线性diophantine equations系统。 Felix Lazebnik提供了Systems of Linear Diophantine Equations的快速谷歌搜索。在该文件中，作者考虑了以下问题：

给定线性方程组Ax = b，其中A = a（i，j）是具有整数项的m×n矩阵，并且b是具有整数分量的m×1列向量，系统是否具有整数解，即具有整数分量的n×1解向量x？

Answer 2

您应该使用专门的整数问题求解器（请注意整数问题甚至不易解决）。 openopt是一个包，例如应该为整数二次优化提供良好的包装，就像你正在做的那样。尝试使用线性代数根本无法直接为您提供正确的解决方案。

你的问题可以写成quadratic program，但它是一个integer，所以使用openopt或其他一些模块。由于它是一个非常简单，不受约束的，也许还有其他方法。但对于初学者来说，它起初并不是一个简单的问题，而且还有openopt等程序可以有效地解决这类问题。

Answer 3

当您转换为int时，元素的小数部分会被截断，因此它会向下舍入。

a = np.array([[1,0], [0,1], [-1,1]])
b = np.array([1,1,0])

x = np.linalg.lstsq(a,b)[0]

结果：

>>> x
array([ 1.,  1.])
>>> x[0]
0.99999999999999967
>>> x[1]
1.0000000000000002
>>> x.astype(int)
array([0, 1])
>>> map(int, x)
[0, 1]
>>> np.array([1.,1.]).astype(int) # works fine here
array([1, 1])

Answer 4

我可能误解了你的问题，但我认为你只需要round和astype(int)的组合？

EG

a = np.array([[1,0], [0,1], [-1,1]])
b = np.array([1,1,0])

x = np.linalg.lstsq(a,b)[0]
print x.round().astype(int)

Answer 5

+1到seberg，这里有一个反例来说明你不应该映射： （对不起，这是matlab风格，但你很容易pythonize）

a =
     3     0
     0     3
     1     1
b = 
    2.71
   11.7
    0.5
x = a\b =
    0.5121
    3.5088
round(x) =
    1
    4
norm(a*round(x)-b) = 4.5193
norm(a*[0;4]-b) = 4.4367
norm(a*[1;3]-b) = 4.4299

Answer 6

我需要这样做并最终将由Keith Matthews编写的PHP程序移植到Python中，该程序可以在http://www.numbertheory.org/php/php.html上找到。我最初使用Numpy数组但遇到了整数溢出的问题，因此切换到使用任意精度数值表示的Sympy矩阵。

该代码在MIT许可证下在https://github.com/tclose/Diophantine的GitHub上发布，所以请随意使用它，如果遇到任何问题请告诉我（对不起，没有更好的文档记录）。主分支使用Sympy，但您可以在'numpy'分支中访问原始的Numpy实现，这对于合理稀疏的系统似乎没问题。

如果您最终将其用于科学出版物，请引用Keith的论文（并且可能添加指向GitHub回购的链接）。

Answer 7

有一种方法叫做block lanczos.这可以在有限的领域内得到答案。您可以找到针对此特定问题的块lanczos解算器。