核心概述
GF(2) 线性求解聚焦于在模 2 的线性代数体系中求解 Ax=b，结合按位异或/与等位运算实现消元与回代，以适配仓库中线性方程求解家族的模 2 特例。
原文引述
KACTL algorithms should be: useful, short, fast enough, well tested, and if relevant, readable and easy to modify. They should not be overly generic, since code is manually typed and that just adds overhead. ——摘自 kactl/README.md
展开阐述
-
定义与背景
- 模 2 域（GF(2)）中，元素仅有 {0,1}，加法对应异或 XOR，减法与加法等价，乘法为按位与 AND（在标量与位块层面）；求解线性方程可视作对行的异或线性组合。
- 本节点与 114-数值算法-线性方程求解、115-数值算法-线性方程求解II 形成同类方法在不同域上的特化；适用于布尔/二值约束、子集状态转移等场景。
-
接口与输入输出语义（按仓库约定）
- 典型接口（据约定风格）：
- solveGF2(A, b) → x 或指示无解/多解；其中 A 为 n×m 的 0/1 系数矩阵，b 为 n 维 0/1 向量，x 为 m 维 0/1 向量。
- 语义：
- 返回任一可行解；如系统有多解，可返回一组自由变量取 0 的规范解或显式报告秩与自由度。
- 典型接口（据约定风格）：
-
核心流程与关键要点
- 行主元选择：逐列寻找可作为主元的行（该列存在 1）；若存在则交换至当前行。
- 归一与消元：在 GF(2) 下无需“缩放”，仅对其它行进行按位异或以清零该列。
- 自由变量与回代：若某列无主元，则对应变量为自由变量；回代阶段同样以异或组合表达解。
- 位运算加速：可将每行压成若干机器字（如 64 位块），用按位 XOR 批量消元；该思路与 114-数值算法-线性方程求解 中“模数域将除法替换为乘逆元”的精神保持一致，但在 GF(2) 下更为简洁。
-
数值与实现注意
- 稀疏/稠密：对稠密矩阵采用位块批处理；对稀疏矩阵可保留稀疏结构以减少异或次数。
- 秩与可解性：消元后若出现 0=1（矛盾行），则无解；否则根据秩与变量数判断是否唯一解。
- 与实数/模 p 的对比：GF(2) 下操作简化，无需除法与浮点稳定性考量；但需要管理自由变量的组合。
-
复杂度与边界条件
- 朴素异或消元在 n×m 规模下与常规高斯消元量级一致；位块优化将常数显著降低（依实现与块宽度）。
- 边界：空矩阵/零行、全 0 列（对应自由变量）、b 为全零（始终可解，包含零解）。
-
与相邻技术的取舍对比
- 若需多次对同一系数矩阵求解，参见 115-数值算法-线性方程求解II 的分解/复用思路在 GF(2) 的适配。
- 若目标是显式求逆而非求解，参见 107-数值算法-矩阵求逆，在 GF(2) 可做对应的按位版本。