我有一个有点数学问题.我有一堆位域,并且想要计算它们的哪个子集以xor在一起以实现某个其他位域,或者如果没有办法,则发现不存在这样的子集.
我想使用免费的库而不是原始代码来做这件事,我更喜欢使用Python绑定的东西(使用Python的内置数学库也是可以接受的,但我想把它移植到多种语言最终).同样最好不要因为必须将每个位扩展到它自己的字节而占用内存.
进一步澄清:我只需要一个解决方案.我的矩阵与稀疏相反.我非常有兴趣将运行时保持在绝对最小值,因此强烈建议使用算法级别的方法来反转矩阵.此外,特定的给定位域是输出的位域非常重要,因此只需找到xor到0的子集的技术就不会完全削减它.
我一般都知道高斯消除.我试图避免从头开始这样做!
交叉发布到mathoverflow,因为不清楚这个问题的正确位置是什么 - https://mathoverflow.net/questions/41036/how-to-find-which-subset-of-bitfields-xor-to -another-位域
从数学上来说，在F_2字段中，两位的异或可以被视为加法。
您想要求解 F_2 域中的一组方程。对于具有位 (a_0, a_1, ... a_n)、(b_0, b_1, ..., b_n)、(c_0, c_1, ..., c_n)、(r_0, r_1, ..., r_n) 的四个位字段），你得到方程：
x * a_0 + y * b_0 + z * c_0 = r_0
x * a_1 + y * b_1 + z * c_1 = r_1
...
x * a_n + y * b_n + z * c_n = r_n
（您在其中查找 x、y、z）。
您可以将其编程为一个简单的整数线性问题glpk，可能lp_solve（但我不记得它是否适合）。不过，它们的工作速度可能会非常慢，因为它们正在尝试解决更普遍的问题。
经过谷歌搜索一段时间后，似乎这个页面可能是寻找代码的良好开始。从描述来看，这似乎Dixon是LinBox一个很好的选择。
无论如何，我认为在 mathoverflow 上询问可能会给你更准确的答案。如果您这样做，请在此处链接您的问题。
更新： Sagemath使用M4RI来解决此问题。这（对我来说）是一个非常好的推荐。