模2 python代码中的高斯消除

Question

我想知道模2中的高斯消除(或者甚至通常以模k为目的)是否已经在某处实现过,因此我不必重新发明轮子并仅使用可用资源？

Answer 1

您正在寻找的算法的伪代码存在并且是：

\n\n

    // A is n by m binary matrix\n    i := 1 // row and column index\n    for i := 1 to m do // for every column\n      // find non-zero element in column i, starting in row i:\n      maxi := i\n      for k := i to n do\n        if A[k,i] = 1 then maxi := k\n      end for\n      if A[maxi,i] = 1 then\n        swap rows i and maxi in A and b, but do not change the value of i\n        Now A[i,i] will contain the old value of A[maxi,i], that is 1\n        for u := i+1 to m do\n          Add A[u,i] * row i to row u, do this for BOTH, matrix A and RHS vector b\n          Now A[u,i] will be 0\n        end for\n     else\n       declare error \xe2\x80\x93 more than one solution exist\n     end if\n   end for\n   if n>m and if you can find zero row in A with nonzero RHS element, then\n     declare error \xe2\x80\x93 no solution.\n   end if\n   // now, matrix A is in upper triangular form and solution can be found\n   use back substitution to find vector x\n

\n\n

摘自此pdf

\n\n

二进制算术意味着模 2 的算术，如果我没记错的话，这就是您在问题中寻找的内容。

\n\n

不幸的是我不会用Python编写代码，但是如果你熟悉Python，你可以简单地用你自己的方式将上面的伪代码逐行翻译成Python，以方便你，这个任务应该既不困难也不困难。。

\n\n

我用google搜索了“高斯消去模2 python”，但没有找到你要找的python代码，但我认为这是好的，因为在翻译过程中你可能会更好地理解算法和方法。

\n\n

编辑 1：如果您也熟悉 C# 并且将 C# 翻译成 Python 并不费力，那么 Michael Anderson 对这个问题的回答回答也可能对您有所帮助。

\n\n

编辑2：发布答案后，我继续搜索并发现了这个

\n\n

“在任何域上”意味着“在模 2 上”，甚至对于任何 k≥2 来说“在模 k 上”。

\n\n

它包含 Java 版本和Python 版本的源代码版本的源代码。

\n\n

根据我给你的Python版本的最后一个链接，fieldmath.py包含类BinaryField，它假设是模2。

\n\n

享受！

\n\n

我只是希望高斯-乔丹消元法和高斯消元法不是两个不同的东西。

\n\n

编辑3：如果你也熟悉 VC++ 并且将 VC++ 翻译成 Python对你来说并不费力，那么你也可以尝试这个。

\n\n

我希望这能很好地回答你的问题。

\n