Linnea: Automatic Generation of Efficient Linear Algebra Programs
核心思路
把矩阵性质、代数变换、分解条件和计算内核编码为可检查的知识。从高层线性代数公式出发，推导中间量的性质，搜索不同但数学等价的计算路径，最后生成 BLAS／LAPACK 调用程序。
1. 背景与问题
一个数学公式通常对应很多种实现。直接从左往右计算、显式求逆、忽略矩阵结构，可能得到正确但很慢的程序。高效实现需要同时理解代数性质和计算库：哪些项可重写、哪些中间矩阵正定、何时可以使用特定分解或三角求解。
知识需要在推导途中发挥作用，而不只是出现在程序旁边的解释里。这使 Linnea 成为一个具体的领域知识运用案例。
第 2 节讨论的已有路线包括：
| 路线 | 已有能力 | 本文进一步关注什么 |
|---|---|---|
| BLAS／LAPACK 与 Matlab、Julia、Eigen、Armadillo | 提供高效内核和高层接口，部分利用矩阵性质 | 跨整个表达式搜索不同等价算法，而非只优化已确定的单次调用。 |
| Clak 等线性代数代码生成 | 已利用性质、分解与代数规则生成算法 | 更灵活地处理输入表达式，并用图搜索组织推导与复用。 |
| Cl1ck 等算法推导 | 从形式描述推导特定类型的矩阵算法 | 问题范围和生成层次不同，不能仅凭都“自动生成”就视为同一任务。 |
| 编译器公共子表达式与优化 | 消除已有程序中的冗余 | 还需要识别代数等价表达式、性质和替代分解。 |
Linnea 是领域专用的符号系统，并未使用 LLM。它展示的是：当知识表示足够精确时，怎样把专业理解变成推导和实现选择。
2. 方法与创新
输入公式，也输入可用前提
输入包含表达式、操作数形状及性质，如满秩、对称正定、对角、三角。内部以符号表达式表示问题，以带条件的模式表示可用内核。
例如矩阵乘加可匹配到 gemm；专用内核还需检查形状和性质约束。矩阵乘法保留操作数顺序，不能因为模式匹配支持交换操作，就把矩阵乘法当作可交换。
推导中间性质，开放新的合法选择
考虑广义最小二乘：
已知 对称正定， 满列秩且行数大于列数，便可推出 也对称正定。这不是输入里独立声明的事实，而是从前提推导出的中间结论。
理解这一点的数学理由是：对非零 ，满列秩保证 ，因此
知道 正定后，就可以选择 Cholesky 而不是更一般的 LU 分解。知识形成一条可追查的链：输入前提 → 中间性质 → 合法分解 → 具体内核。
在推导图中搜索算法
原论文图 3，v1 PDF 第 6 页。图中每条边对应一个或多个计算步骤；这是整体搜索空间的一小部分。
图节点表示尚待计算的表达式，边表示选定的内核或分解步骤。从原表达式到全部求值完成的路径，就是一个算法。
搜索会尝试结合律、分配律、公共子表达式、逆与转置关系，以及满足条件的矩阵分解。逆符号可以表示线性系统求解需求，最终程序不必真的形成逆矩阵。
系统使用定制 best-first 搜索，优先较有希望的后继，尽快得到首个可用解，再用已有解的代价限制后续搜索。给予更多时间，可找到更好的候选；这是一种预算内搜索，不保证短时间遍历所有算法。
识别等价状态，复用已有推导
不同变换顺序可能回到相同表达式。Linnea 使用规范形式、统一中间量和分支合并，减少重复探索。若通向合并节点的路径变便宜，相关代价和后续搜索也要更新，不能只在第一次访问时固定结果。
实现阶段还处理内核覆盖输入、临时变量以及三角／对称数据的存储格式，才能把抽象算法翻译成实际库调用。
代价模型负责选择，实际性能仍需核对
论文主要以 FLOPs 作为搜索代价。内核的计算量公式是知识的一部分，例如矩阵乘的计算量由维度决定。
FLOPs 易组合，但真实时间还受内核效率、线程扩展、数据格式转换与内存行为影响。作者明确指出，任意内核序列的性能不能由单个内核时间简单拼出；数值稳定性分析同样不能直接逐段相加。
贡献是将领域约束、性质推导、代数重写、内核匹配与可复用图搜索连为生成流程。代数等价性与运行代价是两个层面，搜索目标也不等同于数值稳定性保证。
3. 应用与效果
实验包含 25 个应用问题＋100 个随机表达式，覆盖图像／信号处理、统计和正则化。比较对象包括 Matlab、Julia、Eigen、Armadillo 的直接写法与推荐写法，后者避免了部分显式求逆等问题。
在论文的 Xeon／MKL 环境下，Linnea 程序在单线程约 91%、24 线程约 82% 的案例中最快；125 个测试问题的搜索首解均在 1 秒以内（第 5 节）。这些是当时硬件、版本、输入规模下的结果。
改写公式，比逐个加速算子更重要
图像恢复中有表达式 。按字面先算 会产生昂贵矩阵乘；重写为 后，计算 主要使用矩阵—向量乘。论文在相应问题中展示了从立方级到平方级计算量的变化，这依赖该表达式及尺寸条件。
还有一项很适合工程分析的反例：某候选算法比 FLOPs 最少方案多约 4% 运算，却在 24 线程下快约 27%。原因是更有效率的矩阵乘替代了一部分分解和三角求解。更少运算不是更短时间的充分条件。
适用边界
系统依赖人工编码的性质、模式和变换，输入前提错误时也会导致错误选择。该版本主要针对受限的稠密实数线性代数；稀疏、复杂并发、加速器等属于扩展方向。数学等价不保证浮点数值行为同样良好，FLOPs 最优也不保证实际最快。
对 infra 专业知识库的启发（阅读判断）
优先找能成为可检查规则的知识：形状与布局约束、资源核算、通信量关系、合法配置前提。让每次实现选择保留“依据哪些性质、用了哪条变换”，并把正确性规则与经验代价模型分开。它提供了比“把资料喂给 LLM”更具体的知识运用样例，但可覆盖的领域范围也更受限制。