我应该如何在 C/C++ 中计算 GF(2) 上矩形稀疏矩阵的空值 space？
How should I compute the null space of a rectangular sparse matrix over GF(2) in C/C++?
更新：我最终没有使用 Eigen 并实现了我自己的 GF(2) 矩阵表示，其中每一行都是一个整数数组，整数的每一位代表一个条目。然后我使用带有位操作的 modified Gaussian Elimination 来获得所需的向量
我目前有一个（大）矩形稀疏矩阵，我正在使用 Eigen3 存储它，我想在 GF(2) 上找到（右）空值 space。我四处研究并找到了一些可能的方法：
- （修改）高斯消元
这意味着只需使用某种形式的高斯消去法来找到保留空值space 的矩阵的简化形式，然后从中提取空值space。虽然我知道如何手动执行此操作，但我对如何实际执行此操作一无所知。
- SVD 分解
- 二维码分解
我不熟悉这些，但根据我的理解，可以从矩阵的分解形式中提取空值的（正交）基向量space。
现在我的问题是：我应该使用哪种方法（即 GF(2) 上的矩形稀疏矩阵）不涉及转换为密集矩阵？如果有很多方法，在性能和易于实施方面有什么建议？
除了 Eigen，我也愿意使用其他库。
对于上下文，我正在尝试为因式分解算法（例如在二次筛法中）找到组合等价关系。另外，如果可能的话，我想在未来研究并行化这些算法，所以如果有一种方法可以做到这一点，那就太好了！
更新的答案 - 感谢哈罗德：QR 分解一般不适用于您的情况。
见实例
https://math.stackexchange.com/questions/1346664/how-to-find-orthogonal-vectors-in-gf2
我错误地认为，QR在这里适用，但理论上并非如此。
如果您仍然对 QR 算法的详细信息感兴趣，请打开一个新线程。
我们称问题矩阵为M。然后（如有错误请指正）：
GF(2) 意味着 M 等价于位矩阵 - 每个元素可以有两个值之一。
GF(2) 的算术就像非负数的整数算术，但是对 2 进行模运算，所以加法是按位 XOR，乘法是按位 AND。 GF(2) 有什么确切的元素并不重要——它们都等同于位。
GF(2)中的向量是线性无关的，只要它们不相等，或者只要它们至少相差一点，或者v_1 + v_2 ≠ 0（因为 GF(2) 中的加法是布尔异或）。
根据定义，（右）零空间跨越矩阵转换为 0 的基向量。向量 v 将在零空间中，如果一个乘以每个第 j 列M与v的第j位相加，结果为零
我至少看到两种解决方法。
在位操作上做密集高斯消元，组织数据写循环，让编译器全部矢量化，对512位数据类型进行操作。您可以使用 Compiler Explorer on godbolt.org 轻松检查矢量化是否发生，例如使用 AVX512 指令。当然，线性增益最终会随着问题的平方缩放而消失，但是与基于天真的 bool 的实现相比，性能提升将是巨大的，可能足以满足您的需求。稀疏性增加了一个可能的复杂性：如果矩阵不能以密集的表示轻松地适合内存，那么必须设计一个合适的表示，使高斯消元法表现良好。 需要了解更多有关您处理的矩阵的信息。一般来说，如果实现正确，行操作将在内存带宽上执行，大约为 1E10 elements/s，因此 1E3x1E3 M 最多应该处理大约一秒.
由于问题等价于一组布尔方程，使用SAT求解器（布尔可满足性问题求解器）逐步生成零空间。初始方程组为M×v=0且v≠0，其中v 是位向量。 运行 SAT 直到它找到一些 v，我们称它为 v_i。然后添加约束 v ≠ v_i，并再次 运行 SAT - 在每次迭代中添加约束。也就是说，k-th 迭代具有约束条件 v ≠ 0，v ≠ v1, ... v ≠ v(k-1)。
由于所有不同的位向量也是线性无关的，不等式约束将强制增量生成零空间基向量。
现代 SAT 擅长解决布尔方程多于变量的稀疏问题，所以我想这会很有效——矩阵越稀疏越好。应该对问题进行预处理以删除 M 中的所有零列，以最大限度地减少组合爆炸。 开源 SAT 求解器可以轻松处理 1M 变量问题 - 因此，对于稀疏问题，您实际上可以用 M[=76= 中的 100k-1M 列来求解]，每行大约有 10 个“一”。因此，平均每行有 10 个“1”的 1Mx1M 稀疏矩阵对于常见的 SAT 求解器来说是一项合理的任务，我想最先进的技术可以处理 10Mx10M 及以上的矩阵。
此外，您的应用程序非常适合增量求解器：您找到一个解决方案、停止、添加约束、恢复等等。所以我想你可能会得到很好的结果，并且有几个很好的开源求解器可供选择。
既然你已经使用了 Eigen，这个问题至少会符合 SparseMatrix 字节大小元素的表示，所以就 SAT 而言，这不是一个很大的问题。
我想知道这个零空间基础发现是否是一个覆盖问题的案例，可能是放松的。这些算法有一些不错的算法，但问题始终是专门的算法是否会比仅仅将 SAT 扔给它然后等待它更好地工作，可以这么说。
更新：我最终没有使用 Eigen 并实现了我自己的 GF(2) 矩阵表示，其中每一行都是一个整数数组，整数的每一位代表一个条目。然后我使用带有位操作的 modified Gaussian Elimination 来获得所需的向量
我目前有一个（大）矩形稀疏矩阵，我正在使用 Eigen3 存储它，我想在 GF(2) 上找到（右）空值 space。我四处研究并找到了一些可能的方法：
- （修改）高斯消元
这意味着只需使用某种形式的高斯消去法来找到保留空值space 的矩阵的简化形式，然后从中提取空值space。虽然我知道如何手动执行此操作，但我对如何实际执行此操作一无所知。
- SVD 分解
- 二维码分解
我不熟悉这些，但根据我的理解，可以从矩阵的分解形式中提取空值的（正交）基向量space。
现在我的问题是：我应该使用哪种方法（即 GF(2) 上的矩形稀疏矩阵）不涉及转换为密集矩阵？如果有很多方法，在性能和易于实施方面有什么建议？
除了 Eigen，我也愿意使用其他库。
对于上下文，我正在尝试为因式分解算法（例如在二次筛法中）找到组合等价关系。另外，如果可能的话，我想在未来研究并行化这些算法，所以如果有一种方法可以做到这一点，那就太好了！
更新的答案 - 感谢哈罗德：QR 分解一般不适用于您的情况。
见实例
https://math.stackexchange.com/questions/1346664/how-to-find-orthogonal-vectors-in-gf2
我错误地认为，QR在这里适用，但理论上并非如此。
如果您仍然对 QR 算法的详细信息感兴趣，请打开一个新线程。
我们称问题矩阵为M。然后（如有错误请指正）：
GF(2) 意味着 M 等价于位矩阵 - 每个元素可以有两个值之一。
GF(2) 的算术就像非负数的整数算术，但是对 2 进行模运算，所以加法是按位
XOR，乘法是按位AND。 GF(2) 有什么确切的元素并不重要——它们都等同于位。GF(2)中的向量是线性无关的，只要它们不相等，或者只要它们至少相差一点，或者v_1 + v_2 ≠ 0（因为 GF(2) 中的加法是布尔异或）。
根据定义，（右）零空间跨越矩阵转换为 0 的基向量。向量 v 将在零空间中，如果一个乘以每个第 j 列M与v的第j位相加，结果为零
我至少看到两种解决方法。
在位操作上做密集高斯消元，组织数据写循环，让编译器全部矢量化，对512位数据类型进行操作。您可以使用 Compiler Explorer on godbolt.org 轻松检查矢量化是否发生，例如使用 AVX512 指令。当然，线性增益最终会随着问题的平方缩放而消失，但是与基于天真的
bool的实现相比，性能提升将是巨大的，可能足以满足您的需求。稀疏性增加了一个可能的复杂性：如果矩阵不能以密集的表示轻松地适合内存，那么必须设计一个合适的表示，使高斯消元法表现良好。 需要了解更多有关您处理的矩阵的信息。一般来说，如果实现正确，行操作将在内存带宽上执行，大约为 1E10 elements/s，因此 1E3x1E3 M 最多应该处理大约一秒.由于问题等价于一组布尔方程，使用SAT求解器（布尔可满足性问题求解器）逐步生成零空间。初始方程组为M×v=0且v≠0，其中v 是位向量。 运行 SAT 直到它找到一些 v，我们称它为 v_i。然后添加约束 v ≠ v_i，并再次 运行 SAT - 在每次迭代中添加约束。也就是说，k-th 迭代具有约束条件 v ≠ 0，v ≠ v1, ... v ≠ v(k-1)。
由于所有不同的位向量也是线性无关的，不等式约束将强制增量生成零空间基向量。
现代 SAT 擅长解决布尔方程多于变量的稀疏问题，所以我想这会很有效——矩阵越稀疏越好。应该对问题进行预处理以删除 M 中的所有零列，以最大限度地减少组合爆炸。 开源 SAT 求解器可以轻松处理 1M 变量问题 - 因此，对于稀疏问题，您实际上可以用 M[=76= 中的 100k-1M 列来求解]，每行大约有 10 个“一”。因此，平均每行有 10 个“1”的 1Mx1M 稀疏矩阵对于常见的 SAT 求解器来说是一项合理的任务，我想最先进的技术可以处理 10Mx10M 及以上的矩阵。
此外，您的应用程序非常适合增量求解器：您找到一个解决方案、停止、添加约束、恢复等等。所以我想你可能会得到很好的结果，并且有几个很好的开源求解器可供选择。
既然你已经使用了 Eigen，这个问题至少会符合
SparseMatrix字节大小元素的表示，所以就 SAT 而言，这不是一个很大的问题。我想知道这个零空间基础发现是否是一个覆盖问题的案例，可能是放松的。这些算法有一些不错的算法，但问题始终是专门的算法是否会比仅仅将 SAT 扔给它然后等待它更好地工作，可以这么说。