小尺寸矩阵快速乘法：基于开源翻转图框架发现新算法 Fast Matrix Multiplication in Small Formats: Discovering New Schemes with an Open-Source Flip Graph Framework
开源翻转图框架在680种格式中改进79种矩阵乘法秩
前置知识
张量秩与矩阵乘法复杂度
对于将 $A \in \mathbb{F}^{m \times n}$ 与 $B \in \mathbb{F}^{n \times p}$ 相乘的任务，最少乘法数称为'秩'（rank），对应矩阵乘法张量 $\langle m,n,p \rangle$ 的分解。平凡算法需要 $mnp$ 次乘法，而 Strassen 1969 年发现 $2 \times 2 \times 2$ 只需 7 次，使复杂度指数 $\omega < 3$。寻找更小秩是算法与代数复杂性领域的核心问题。
本文的所有工作都围绕'寻找更小秩'展开，必须先理解秩的代数含义与 $\omega$ 的关系，才能看懂为何 $4 \times 4 \times 10$ 只需 115 次乘法（$\omega \approx 2.80478$）能被称为突破。
Brent 方程
Brent 方程是判定三组系数张量 $U \in \mathbb{F}^{r \times m \times n}$、$V \in \mathbb{F}^{r \times n \times p}$、$W \in \mathbb{F}^{r \times m \times p}$ 是否构成合法矩阵乘法方案的约束系统：$\sum_{l=1}^{r} u^{(l)}_{i_1 i_2} v^{(l)}_{j_1 j_2} w^{(l)}_{k_1 k_2} = \delta_{i_2 j_1} \delta_{i_1 k_1} \delta_{j_2 k_2}$。这是多线性方程组，构成算法发现问题的数学基础。
Brent 方程是 SAT 求解、约束规划、翻转图搜索共同作用的代数对象；理解其双线性结构才能明白为何 Hensel 提升在每一步需要解欠定线性系统。
翻转图方法（Flip Graph）
由 Kauers 等人提出的搜索范式，把所有合法矩阵乘法方案视作图节点，把保持合法性的局部变换（如 flip、plus、split、reduction、sandwiching）视作边，通过随机游走或图探索寻找低秩方案。Meta-flip graph 进一步允许跨维度变换（merge、product、extend、project）。
这是本文搜索算法的核心骨架，与 SAT/RL/数值方法形成对比；读懂 flip、plus、reduce 三类局部算子对理解方法流程至关重要。
系数环（$\mathbb{Z}_2$, $\mathbb{Z}_3$, $\mathbb{Z}_T$, $\mathbb{Z}$, $\mathbb{Q}$）
方案中线性组合允许的数值集合。$\mathbb{Z}_T = \{-1,0,1\}$ 是工程上最理想的（仅加减），$\mathbb{Z}_2$、$\mathbb{Z}_3$ 模运算分别用于发现特征 2/3 域上的方案，再通过 Hensel 提升回一般域。$\mathbb{Q}$ 方案常含大整数或分数，硬件实现开销大。
本文的关键贡献之一正是把大量原本需要分数的方案改写为 $\mathbb{Z}_T$，必须理解系数环差异才能体会工程价值。
Hensel 提升与有理重构
把模 $p^k$ 环上的合法方案逐步提升到模 $p^{k+1}$ 的过程。每一步需要求解欠定线性系统 $Jx \equiv (T - U \otimes V \otimes W) \pmod{p^k}$，再对系数做有理重构得到小分母分数。$p=2$ 时还可用'约束式提升'策略：仅尝试保持系数为 0 或 1。
本文 $\mathbb{Z}_2 \to \mathbb{Z}_T$ 的关键链路就是 Hensel 提升，若不理解欠定系统的多解性就无法读懂第 4.6 节和第 7.5 节。
研究动机
小尺寸矩阵乘法在科学计算与机器学习中是基础构件（被 Strassen、AlphaTensor 等大算法递归调用），其乘法次数（秩）直接决定硬件效率。然而当前最优秩的算法往往依赖大整数或分数（如 $3 \times 3 \times 6$ 的已知最优秩 40 方案含 $\pm 1/8$ 系数），难以在 FPGA/GPU 上高效实现。纯 SAT 求解在 $(2,2,2:7)$ 只需几秒，到 $(3,3,3:23)$ 则需要数天无解；AlphaTensor 类强化学习方法虽能找到新算法，但系数往往不实用；Smirnov 的数值方法求出的方案也常需分数。Sedoglavic 在线目录追踪了 5426 种格式的已知最优秩，但绝大多数没有 $\{-1,0,1\}$ 系数版本。
本文的目标是构建一个纯 C++、零外部依赖、易复现的翻转图搜索框架，覆盖 $\mathbb{Z}_2$、$\mathbb{Z}_3$、$\mathbb{Z}_T$ 三种系数环，使用位级编码与 OpenMP 并行实现大规模探索。具体目标包括：(1) 改进尽可能多格式的已知最优秩；(2) 把已知有理或整数方案改造为 $\mathbb{Z}_T$ 形式；(3) 把分数方案改造为整数方案；(4) 通过 12–96 核的实验验证框架有效性与可扩展性。
与已有工作不同的是，已有翻转图工具通常局限于 $\mathbb{Z}_2$，对 $\mathbb{Z}_T$ 系数的工程价值关注不足；Hensel 提升部分常需要繁琐的手动干预；多数实现缺乏 OpenMP 并行，难以在普通硬件上做数十亿次随机游走迭代。本文的核心切入点是：把 $\mathbb{Z}_T$ 作为一等公民嵌入翻转图搜索，配合位级编码的极致性能与受限的 Hensel 提升策略，使得在笔记本/工作站规模（数十核）就能复现甚至超越以前只能在集群上完成的结果。
核心方法
方法整体思路是：把矩阵乘法方案编码为三组位向量张量 $U,V,W$，通过随机游走在翻转图上反复施加局部变换（flip / expand / reduction / sandwiching）来逐步降低秩。直觉上，每一次 flip 都会合并两行相同的乘法项，等价于一次'恒等变换'；当 flip 受阻时通过 expand 临时增秩以跳出局部最优；当有进展时按概率尝试 reduction/sandwiching 收敛。多个并行的独立 runner 同时探索搜索空间，每过一段无改进时间就 reset 到近期最佳方案池中的一个。整个框架通过分层工具链（flip_graph → meta_flip_graph → find_alternative_schemes → lift → scheme_optimizer）支持固定维数搜索、跨维数搜索、替代方案生成、模环到一般环提升。
本文与已有翻转图方法的本质区别有三点：(1) **统一系数环**——首次把 $\mathbb{Z}_2$、$\mathbb{Z}_3$、$\mathbb{Z}_T$ 在同一框架内处理，且 $\mathbb{Z}_T$ 中发现的方案自动适用于任意域；(2) **位级编码**——把系数向量打包到 uint16/32/64/128 中，单次 flip/plus 操作只需几次位运算，使 $(16,16,16)$ 这样的大方案也能在毫秒级完成单步变换；(3) **受限 Hensel 提升**——对 $\mathbb{Z}_2 \to \mathbb{Z}_4$ 这一关键步骤，强制只在 $\{0,1\}$ 候选中搜索修正量，使得 $\mathbb{Z}_4 \to \mathbb{Z}_T$ 的概率显著提升。配合 flip potential 启发式（候选方案的可翻转对数）与近期改进池重置策略，能在数十核硬件上连续运行一周仍持续发现新秩。
方法步骤详情
完整方法流程分七步。第一步**初始化**：从平凡方案或用户提供的方案文件读入 $U,V,W$ 系数张量。第二步**位级编码**：根据矩阵维度自动选择 uint16/32/64/128，把 $\mathbb{Z}_T$ 拆为符号位与幅度位两张位图，$\mathbb{Z}_3$ 拆为高/低两位。第三步**随机游走**：每个 runner 维护 flipsCount 与 iterationsCount，先尝试 flip（保持秩不变），失败时按概率尝试 expand（plus 或 split 随机选一）以跳出局部最优；flip 成功后按概率调用 reduction 与 sandwiching。第四步**重启机制**：当 flipsCount 超过从分布采样的阈值则强制 expand；当 iterationsCount 超限则从近期改进的循环缓冲池（容量 10）中重置方案，必要时回退到初始方案。第五步**跨维搜索**（meta_flip_graph）：每轮游走结束后以配置概率调用 merge/product/extend/project 改变维度。第六步**替代方案生成**（find_alternative_schemes）：用 flip、expand、sandwiching 制造同维度同秩的不同方案，便于后续比较或初始化。第七步**Hensel 提升**（lift）：从 $\mathbb{Z}_2$ 经 $\mathbb{Z}_4 \to \mathbb{Z}_8 \to \cdots$ 或从 $\mathbb{Z}_3$ 经 $\mathbb{Z}_9 \to \mathbb{Z}_{27} \to \cdots$，每步解欠定线性系统并尝试有理重构；$\mathbb{Z}_2$ 提升时强制候选为 $\{0,1\}$，若仅一个候选可通过有理重构则固定之，否则放开约束。所有工具通过 OpenMP 并行，多线程间用 seed+i 派生独立随机数保证完全可复现。
技术新颖性
技术新颖性体现在三个层面。**算法层面**：把 $\mathbb{Z}_T$ 提升与受限 Hensel 策略系统化地集成到翻转图管线中，使得 $\mathbb{Z}_T$ 不仅是搜索目标，也是初始合法环；以 flip potential 作为启发式选择搜索候选属于新观察。**工程层面**：把单个方案完整位级打包到 ≤128 位整数中，单次 flip 操作从 $O(mn)$ 降为 $O(1)$，使 $(16,16,16)$ 方案单步迭代仅需亚毫秒，数十亿次迭代在数日内即可完成；零依赖纯 C++17 实现保证任何 g++ 都能编译。**实验规模层面**：在 12 核笔记本、20 核工作站、96 核集群上跑出总计数十亿次迭代，覆盖 680 种格式、改进了 79 种已知秩、改写了 93 种方案的系数环——其工程规模在同类开源工具中处于领先地位。
实验结果
实验产出三项核心成果。**(1) 79 种秩改进**：跨越 $4 \times 4 \times 10$ 到 $15 \times 15 \times 16$，全部打破了 Sedoglavic 目录中记录的已知最优上界。最引人注目的是 $4 \times 4 \times 10$ 格式——以前需要 120 次乘法（有理系数），本文通过 $\mathbb{Z}_T$ 系数方案降至 115 次，对应 $\omega = 3 \log 115 / \log 160 \approx 2.80478$，严格优于 Strassen 指数 $\log_2 7 \approx 2.807$。其它代表性改进包括 $4 \times 5 \times 12$ 从 179 ($\mathbb{Z}_T$) 降至 174、$5 \times 5 \times 12$ 从 220 ($\mathbb{Z}$) 降至 208、$9 \times 10 \times 10$ 从 600 ($\mathbb{Z}$) 降至 597、$13 \times 14 \times 16$ 从 1825 ($\mathbb{Q}$) 降至 1806。**(2) 93 种 $\mathbb{Z}_T$ 替代方案**：以前只用有理/整数系数达到的秩，本文用 $\{-1,0,1\}$ 系数复现，包括 $3 \times 3 \times 7$（49）、$3 \times 4 \times 12$（108）、$6 \times 9 \times 9$（342）、$10 \times 10 \times 11$（719）等。**(3) 68 种纯整数替代方案**：以前需要分数的方案被改写为整数系数，如 $2 \times 5 \times 7$（55）、$3 \times 5 \times 13$（147）、$5 \times 7 \times 9$（229）、$6 \times 13 \times 16$（819）。**(4) 整体统计**：680 种格式中 $\mathbb{Z}_T$ 占 40.6%（276 种）、整数占 17.2%（117 种）、有理占 42.2%（287 种）；29 种格式的秩低于递归应用 Strassen 所得，其中 1 种（本工作的 $4 \times 4 \times 10$）为本工作新发现。**(5) 现象级观察**：flip potential（$U,V,W$ 中相同行的对数）与是否能进一步降秩强相关——flip potential 高（60–120 对）的方案几乎都能继续优化，而有些 flip potential 极低的方案却对所有尝试无反应；某些维度组合（如 $m \times n \times 12$）存在系统性下凹点，可能源于 $3 \times 3 \times 6$ 或 $3 \times 4 \times 6$ 经块构造传播，但完整机制仍是开放问题。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| 4×4×10 矩阵乘法秩 | 乘法次数 / 指数 ω | 115 次乘法（ZT 系数），ω ≈ 2.80478 | 120 次乘法（Q 系数），Sedoglavic 目录 | 节省 5 次乘法，ω 首次严格低于 Strassen |
| 5×5×12 矩阵乘法秩 | 乘法次数 | 208 次乘法（ZT 系数），ω ≈ 2.80737 | 220 次乘法（Z 系数） | 节省 12 次乘法（≈ 5.5%） |
| 9×10×10 矩阵乘法秩 | 乘法次数 | 597 次乘法（ZT 系数），ω ≈ 2.81897 | 600 次乘法（Z 系数） | 节省 3 次乘法 |
| 13×14×16 矩阵乘法秩 | 乘法次数 | 1806 次乘法（Q 系数），ω ≈ 2.82033 | 1825 次乘法（Q 系数） | 节省 19 次乘法（≈ 1.0%） |
| 10×13×16 矩阵乘法秩 | 乘法次数 | 1326 次乘法（ZT 系数），ω ≈ 2.82322 | 1332 次乘法（Z 系数） | 节省 6 次乘法，并改用 ZT 系数 |
| 3×3×6 矩阵乘法秩（开放问题） | 乘法次数 | 42 次乘法（ZT/Z2/Z3 系数停滞点） | 40 次乘法（Q 系数，含 ±1/8） | 未改进；显示 ZT 与 Q 之间存在结构鸿沟 |
| 4×7×15 块构造秩 | 乘法次数 | 307 次乘法（通过 2×2×2 + 7 块乘法） | 无直接基线，作为构造示例 | 演示 51+35+45+40+51+45+40 = 307 的块组合范式 |
局限与改进
**作者承认的局限**：(1) 编码限制——每个矩阵维度乘积 $m \times n \le 128$，仅能覆盖 $11 \times 11 \times 11$ 以内的直接搜索，更大方案只能靠块构造；(2) $\mathbb{Z}_2$ 提升的'约束式'策略可能剪掉通往高 lift 步后才合法的方案路径，$\mathbb{Z}_3$ 提升目前没有任何类似约束；(3) Hensel 提升的解空间选择仍是开放难题，欠定系统的多解性导致大量解只产生大分数系数；(4) 一些格式即使搜索很久也纹丝不动（如 $3 \times 3 \times 6$ 在 $\mathbb{Z}_T$ 上卡在 42 不动），flip potential 启发式无法解释为何某些低 potential 方案也降不下来；(5) 受限于单机 96 核的算力，更大维度搜索难以铺开。**笔者的额外观察**：(a) flip graph 搜索对初始方案依赖明显，论文未深入分析不同种子对最终秩的方差；(b) 实验未给出具体的 wall-clock time per iteration 或每次发现的 CPU 小时成本，难以估算外推到集群的成本收益；(c) 'rank 改进'的定义基于 Sedoglavic 目录，但该目录本身可能存在未公开条目，因此 79 个'改进'是相对于该目录而非绝对最优；(d) $\mathbb{Z}_2 \to \mathbb{Z}_T$ 提升成功率缺乏统计，仅描述'足够多'，不便于复现比较。
独立分析的弱点
**独立观察到的弱点**：(1) **框架的 $\mathbb{Z}_T$ 偏向性**——本文强项在 $\mathbb{Z}_T$ 搜索，但论文中明确承认 $\mathbb{Z}_3 \to \mathbb{Z}_T$ 提升仍缺乏约束式策略；可改进方向是把约束式 Hensel 推广到 $\mathbb{Z}_3$，并在每步多枚举几个解而非单一选择。(2) **维度上限过紧**——128 元素限制使得 $\ge 12 \times 12 \times 12$ 几乎所有发现都依赖块构造而非直接搜索；可考虑把系数向量扩展到 SSE/AVX 256/512 位寄存器，或采用稀疏编码，仅对非零位存储。(3) **flip potential 启发式未量化**——文中仅说'高 potential 几乎总能继续优化'，但未给出 ROC 曲线或概率分布；可改进方向是统计 potential 与最终降秩幅度的 Pearson/Spearman 相关性，并在调度时按 potential 动态分配 runner。(4) **缺乏理论保证**——所有进展都是实验性的，没有给出为什么某些 $\mathbb{Z}_T$ 方案在 $3 \times 3 \times 6$ 上不存在的代数判据；近期 [16] 给出了一种'是否可由 sandwiching 转整数'的方法，但本文未将其系统整合。(5) **并行效率瓶颈未明**——OpenMP 并行是循环级并行，但所有 runner 共享同一随机游走算法，未讨论 NUMA 亲和性、内存带宽竞争，可能在大规模部署时出现收益递减；可改进方向是加入 MPI 多节点支持或 GPU 加速。(6) **基准对照不足**——文中几乎没有与 AlphaTensor、DeepMind AlphaEvolve、Smirnov 数值方法的直接对比表，只在文字中提及'AI 系数不实用'，缺少定量基准。
未来方向
**作者提出的方向**：(1) 把框架部署到超算/云平台的数千乃至数百万核，期望在 128 元素限制内对剩余最难格式持续突破；(2) 系统研究 flip potential 启发式在更多格式上的可靠性，建立其作为搜索预算分配指标的统计基础；(3) 探索系数环与最优秩的深层关系，特别是为何 $3 \times 3 \times 6$ 在 $\mathbb{Z}_T$ 上卡在 42 而 $\mathbb{Q}$ 上可达 40；(4) 改进受限 Hensel 提升，枚举更多候选解或引入优化目标（如最小化系数绝对值之和）。**基于成果可延伸的方向**：(a) 把 $\mathbb{Z}_T$ 方案作为 LLM 微调的奖励信号，引导模型生成硬件友好的矩阵乘法代码；(b) 与结构化矩阵乘法（如 Khoruzhii 等人在 13/15 种格式上的工作）结合，把通用 $\mathbb{Z}_T$ 方案映射到 Toeplitz/Hankel/对称矩阵场景；(c) 把块构造与自动分块搜索结合，让框架自主发现新的 $m \times n \times p$ 块分解策略而非依赖人工设计；(d) 把翻转图搜索扩展到其它张量分解问题，如多项式乘法、卷积核分解、注意力机制的快速算法。
复现评估
**复现评估**：本文复现性极佳——(1) 框架代码完全开源（github.com/dronperminov/ternary_flip_graph），纯 C++ 实现仅需 g++ 编译器；(2) 所有发现的方案（含 Table 1–3 中列出的 79+93+68=240 项）单独托管在 github.com/dronperminov/FastMatrixMultiplication，便于直接导入作为初始化或对比；(3) 随机种子完全可控，每个 runner 用 seed+i 派生，跨线程/跨机器都可精确复现；(4) 论文报告了三种硬件平台（12 核 i7-9750H、20 核 Xeon Platinum 8358、96 核 JKU 集群）作为参考；(5) 主要工具包含 flip_graph、meta_flip_graph、find_alternative_schemes、lift、scheme_optimizer 五个 CLI，参数通过命令行传入，无 GUI 依赖。**复现难度**：硬件门槛低（笔记本即可启动 12 核并行），但完整复现 Table 1 中 79 项改进需要约 1 周不间断计算（meta_flip_graph 每天发现 1–5 项）；要复现 $4 \times 4 \times 10$ 的 115 次方案可能需要数十次长跑。文档与示例命令完整，整体属于中等难度可复现实验。
论文图表
