时间戳

首页 > 解决方案 > 我应该如何在 C/C++ 中计算 GF(2) 上的矩形稀疏矩阵的零空间？

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

问题描述

更新：我最终没有使用 Eigen 并实现了我自己的 GF(2) 矩阵表示，其中每一行是一个整数数组，整数的每一位代表一个条目。然后我使用修改后的高斯消除和位运算来获得所需的向量

我目前有一个（大）矩形稀疏矩阵，我使用 Eigen3 存储它，我想在 GF(2) 上找到（右）空空间。我四处研究并发现了一些可能的方法：

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

我对这些不熟悉，但根据我的理解，零空间的（正交）基向量可以从矩阵的分解形式中提取出来。

现在我的问题是：在我的情况下我应该使用哪种方法（即 GF(2) 上的矩形稀疏矩阵）不涉及转换为密集矩阵？如果有很多方法，在性能和易于实施方面会推荐什么？

我也愿意使用除 Eigen 之外的其他库。

对于上下文，我正在尝试为分解算法找到组合等价关系（例如，在二次筛中）。另外，如果可能的话，我想在未来考虑并行化这些算法，所以如果存在允许这样做的方法，那就太好了！

标签： c++linear-algebraeigenfactoring

解决方案

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

  1. GF(2) 意味着M等效于位矩阵 - 每个元素可以具有两个值之一。

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

  3. GF(2) 中的向量是线性独立的，只要它们不相等，或者只要它们至少相差一个位，或者v _1 + v _2 ≠ 0（因为 GF(2) 中的加法是布尔异或）。

根据定义，（右）零空间跨越矩阵转换为 0 的基向量。如果将M的第 j 列与v的第 j 位相乘，将它们相加，则向量v将位于零空间中。结果为零。

我至少看到了两种解决方法。

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

  2. 由于问题等价于一组布尔方程，因此使用 SAT 求解器（布尔可满足性问题求解器）增量生成零空间。初始方程组为M × v = 0 且v ≠ 0，其中v是位向量。运行 SAT 直到找到一些v，我们称之为v _i。然后添加一个约束v ≠ v _i，并再次运行 SAT - 在每次迭代中添加约束。也就是说，第k次迭代有约束v ≠ 0，v ≠ v 1，... v ≠ v (k-1)。

    由于所有不同的位向量也是线性独立的，因此不等式约束将强制增量生成零空间基向量。

    现代 SAT 擅长处理布尔方程多于变量的稀疏问题，所以我想这会很好 - 矩阵越稀疏越好。应该对问题进行预处理以删除M中的所有零列，以最小化组合爆炸。开源 SAT 求解器可以轻松处理 1M 变量问题- 因此，对于稀疏问题，您可以实际求解 M 中的 100k-1M 列，每行大约 10 个“1”。因此，对于普通的 SAT 求解器来说，平均每行有 10 个“1”的 1Mx1M 稀疏矩阵将是一项合理的任务，我想最先进的技术可以处理 10Mx10M 及以上的矩阵。

    此外，您的应用程序非常适合增量求解器：您找到一个解决方案、停止、添加约束、恢复等等。所以我想你可能会得到很好的结果，并且有几个很好的开源求解器可供选择。

    由于您已经使用 Eigen，因此该问题至少适合SparseMatrix字节大小的元素的表示，因此就 SAT 而言，这不是一个很大的问题。

  3. 我想知道这个零空间基础发现是否是一个覆盖问题的案例，可能是放松的。有一些很好的算法可以解决这些问题，但这始终是一个问题，即专门的算法是否会比仅仅扔SAT然后等待它更好地工作，可以这么说。

推荐阅读