c++ - 我应该如何在 C/C++ 中计算 GF(2) 上矩形稀疏矩阵的零空间？

Question

更新:我最终没有使用 Eigen 并实现我自己的 GF(2) 矩阵表示，其中每一行都是一个整数数组，整数的每一位代表一个条目。然后我使用 modified Gaussian Elimination用位操作获得所需的 vector
我目前有一个(大)矩形稀疏矩阵，我使用 Eigen3 存储它，我想在 GF(2) 上找到(右)零空间。我四处研究并找到了一些可能的方法:

(修改)高斯消元

这意味着简单地使用某种形式的高斯消除来找到保留零空间的矩阵的简化形式，然后从中提取零空间。虽然我知道我将如何手动执行此操作，但我对如何实际实现此操作一无所知。

SVD分解

QR分解

我不熟悉这些，但根据我的理解，可以从矩阵的分解形式中提取零空间的(正交)基 vector 。
现在我的问题是:在不涉及转换为密集矩阵的情况下，我应该使用哪种方法(即 GF(2) 上的矩形稀疏矩阵)？如果有多种方法，在性能和易于实现方面会推荐什么？
除了 Eigen 之外，我也愿意使用其他库。
对于上下文，我试图找到分解算法的组合等价关系(例如在 Quadratic Sieve 中)。另外，如果可能的话，我想在 future 研究并行化这些算法，所以如果有一种方法可以实现这一点，那就太好了!

Answer 1

让我们将问题中的矩阵称为 M。 然后(如果我错了，请纠正我):

GF(2) 意味着 M 相当于一个比特矩阵——每个元素可以有两个值之一。

GF(2) 上的算术就像非负数上的整数算术一样，但是是模 2，所以加法是按位 XOR , 乘法是按位 AND . GF(2) 具有什么确切元素并不重要 - 它们都等同于位。

GF(2) 中的 vector 是线性无关的，只要它们不相等，或者它们至少相差一个位，或者 v_1 + v_2 ≠ 0(因为 GF(2) 中的加法是 bool 异或)。

根据定义，(右)零空间跨越矩阵变换为 0 的基 vector 。如果将 M 的每个第 j 列与 v 的第 j 位相乘，对它们求和，并且 vector v 将在零空间中结果为零。
我看到至少有两种方法可以解决这个问题。

在位操作方面进行密集高斯消元，并组织数据并编写循环，以便编译器矢量化所有内容并在 512 位数据类型上进行操作。您可以使用 Compiler Explorer on godbolt.org轻松检查矢量化是否发生，例如使用了 AVX512 指令。当然，线性增益最终会随着问题的平方缩放而失败，但性能比朴素的性能提高bool基于的实现将是大规模的，可能足以满足您的需求。稀疏性增加了一个可能的复杂性:如果矩阵在密集表示中不能舒适地适合内存，则必须设计合适的表示，使高斯消除性能良好。需要更多地了解您处理的矩阵。一般来说，如果实现正确，行操作将在内存带宽上执行，大约为 1E10 个元素/s，因此 1E3x1E3 M 最多应该在大约一秒内处理。

由于该问题等价于一组 bool 方程，因此使用 SAT 求解器( bool 可满足性问题求解器)逐步生成零空间。初始方程组为 M × v = 0 且 v ≠ 0，其中 v 是位 vector 。运行 SAT 直到找到一些 v，我们称之为 v_i。然后添加约束 v≠v_i，并再次运行 SAT - 在每次迭代中添加约束。也就是说，第 k 次迭代具有约束 v ≠ 0，v ≠ v1，... v ≠ v(k-1)。
由于所有不同的位 vector 也是线性无关的，不等式约束将强制零空间基 vector 的增量生成。
现代 SAT 擅长解决 bool 方程多于变量的稀疏问题，所以我想这会很有效——矩阵越稀疏越好。应该对问题进行预处理以删除 M 中的所有零列，以最小化组合爆炸。开源 SAT 求解器可以轻松处理 1M 变量问题 - 因此，对于稀疏问题，您可以实际解决 M 中的 100k-1M 列，每行大约 10 个“一个”。因此，平均每行有 10 个“1”的 1Mx1M 稀疏矩阵对于常见的 SAT 求解器来说是一项合理的任务，我想最先进的技术可以处理 10Mx10M 及更高的矩阵。
此外，您的应用程序非常适合增量求解器:您找到一个解决方案、停止、添加约束、恢复等等。所以我想你可能会得到非常好的结果，并且有几个不错的开源求解器可供选择。
由于您已经使用了 Eigen，因此该问题至少适合 SparseMatrix用字节大小的元素表示，所以就 SAT 而言，这不是一个很大的问题。

我想知道这个零空间基发现是否是覆盖问题的一个例子，可能是放松的。有一些很好的算法可以解决这些问题，但问题始终是，专门的算法是否会比简单地将 SAT 扔给它然后等待它运行得更好，可以这么说。