用Python解决线性整数方程组 [英] Solve system of linear integer equations in Python

问题描述

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

I am looking for a method to solve a system of linear equations in Python. In particular, I am looking for the smallest integer vector that is larger than all zeros and solves the given equation. For example, I have the following equation:

，想解决 .

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

In this case, the smallest integer vector that solves this equation is .

但是，我如何自动确定此解决方案? 如果我使用scipy.optimize.nnls，例如

However, how can I determine this solution automatically? If I use scipy.optimize.nnls, like

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). 这也是正确的，但不是所需的解决方案...

the result is (array([ 0., 0., 0.]), 0.0). Which is also correct, but not the desired solution...

对于某些方面的不准确，我深表歉意. 如果有人对这些细节感兴趣，那么问题出在纸上 用于数字信号处理的同步数据流程序的静态调度"，Edward A. Lee和David G. Messerschmitt， IEEE Transactions on Computers，第一卷. C-36，第1号，第24-35页，1987年1月.

I apologize for being imprecise in certain aspects. If anyone is interested in the details, the problem comes from the paper "Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing", Edward A. Lee and David G. Messerschmitt, IEEE Transactions on Computers, Vol. C-36, No. 1, pp. 24-35, January, 1987.

定理2说

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

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证明之后，他们直接说

Directly after the proof of Theorem 2 they say

可能需要求解null空间中的最小正整数向量.为此，请减少u'中的每个有理项，以使其分子和分母相对质数. Euclid的算法将对此有效.

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可能不是最佳工具.他们的算法通常在浮点中工作，并且不能保证给出精确的答案.

To find the exact solution that you want, numpy and scipy are probably not the best tools. Their algorithms generally work in floating point, and are not guaranteed to give the exact answer.

您可以使用 sympy 来获得此问题的确切答案. sympy中的Matrix类提供方法nullspace()，该方法返回空空间的基向量列表.这是一个示例:

You can use sympy to get the exact answer to this problem. The Matrix class in sympy provides the method nullspace() that returns a list of basis vectors for the nullspace. Here's an example:

In [20]: from sympy import Matrix, lcm

In [21]: A = Matrix([[1, -1, 0], [0, 2, -1], [2, 0, -1]])

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

Get the vector in the nullspace. nullspace() returns a list; this code assumes that the rank of A is 2, so the list has length one:

In [22]: v = A.nullspace()[0]

In [23]: v
Out[23]: 
Matrix([
[1/2],
[1/2],
[  1]])

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

Find the least common multiple of the denominators of the values in v so that we can scale the result to the smallest integers:

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数组，可以执行以下操作:

To convert that result to a numpy array of integers, you can do something like:

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

这篇关于用Python解决线性整数方程组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！