← 返回 PaperDaily
视觉与图像
MIT数学家破译高斯消元增长上限，稀疏奇迹破灭
一篇彻底改写数值分析教科书认知的硬核理论成果。作者证明了完全主元与车房主元下高斯消元增长因子的渐近量级为维度拟多项式，解开了自1940年代延续至今的著名开放问题；同时证明稀疏矩阵下部分主元依然可能指数爆炸，寻找最优行置换还是NP难问题。做科学计算底层和数值算法的读者，这篇值得精读。
龙哥读论文
发布于 2026-09-05 00:31:08
阅读 6
查看原文
原论文信息如下：
高斯消元：从古老算法到现代数值分析的基石 高斯消元法有多古老？1790年前后，高斯为了计算小行星轨道，系统化地整理出了一套消元方法。到今天，你手机里任何一个科学计算App，不管是做电路仿真、图像处理、物理模拟还是机器学习训练，底层几乎都会碰上它或者它的变体。
它的核心思想，简单到令人发指：把未知数一个一个消掉，最后只剩一个变量直接解，然后再一个一个代回去。用矩阵的语言讲，就是把矩阵A拆成下三角矩阵L和上三角矩阵U的乘积，这就是传说中的LU分解
论文的公式(1.1)把这个过程表达得非常紧凑：每一步消元就是在当前子矩阵上做一次类似Schur补的运算，不断缩小矩阵规模。具体来说，设A^(k)为第k步消元前的子矩阵，将其分块为
从计算复杂度的角度看，高斯消元的算术运算量约为(2/3)n³次浮点运算。对于n=1000的矩阵，这大约是6.7亿次运算，在今天的计算机上毫秒级完成。然而，如果数值不稳定导致需要更高精度（比如任意精度算术），计算代价会急剧上升。因此，理解并控制增长因子，不仅关乎数值准确性，也直接关系到计算效率。一个看似微小的数值不稳定，可能迫使算法从双精度切换到四倍精度甚至任意精度，导致计算时间增加几个数量级。这也是为什么增长因子这个看似纯粹的理论概念，实际上对高性能计算实践有着深远影响。
增长因子：决定数值稳定性的关键量 计算机里的数字不是实数，它们是用有限比特存储的浮点数。每一步运算都会引入舍入误差，误差在迭代中会被放大——放大的倍数，就是论文的主角：增长因子（growth factor）
如果增长因子是n²这种多项式级别，双精度浮点基本能扛住。但如果它是2^(n-1)这种指数级别，比如n=100时变成2^99约6×10^29——这么大的数一出现，double的精度直接就废了，算出来的结果没几位有效数字。这就是为什么控制增长因子是数值算法设计的第一优先级。
更具体地说，Wilkinson在1961年给出了著名的误差分析框架：在部分主元高斯消元中，计算得到的解x̂满足(A+ΔA)x̂=b，其中||ΔA||≤p(n)·n·ε·growth(A)·||A||，这里p(n)是一个低次多项式，ε是机器精度。这个不等式清晰地表明，增长因子直接乘以误差上界——增长因子越大，最终解的误差就越大。因此，理解增长因子的行为，本质上就是理解高斯消元在浮点运算下的可靠性边界。
值得注意的是，增长因子与矩阵条件数（condition number）是两个不同的概念。条件数衡量的是问题本身对输入扰动的敏感性，而增长因子衡量的是算法在消元过程中对元素放大的程度。一个条件数很大的矩阵（病态问题）即使使用完全主元策略，也无法获得高精度解；但一个条件数良好的矩阵，如果使用了不恰当的主元策略导致增长因子爆炸，同样会得到灾难性的结果。两者共同决定了最终计算误差的上界，这也是为什么数值线性代数中既要关注问题条件数，也要关注算法稳定性。
主元策略大比拼：从完全主元到随机化策略 既然某些矩阵的增长因子会爆炸，一个自然的想法就是：能不能通过交换行或列，把"坏矩阵"变成"好矩阵"？当然，怎么交换需要一套规则，这就是主元策略（pivoting strategy）
先看最"土豪"的——完全主元（complete pivoting）
再看一个折中方案——车房主元（rook pivoting）
突破性进展：完全主元增长因子的拟多项式下界 这篇论文真正的高光时刻，是对完全主元和车房主元增长因子的渐近行为给出了决定性答案。
先交代点历史背景。1947年，Goldstine和von Neumann发表了一篇名为《Numerical Inverting of Matrices of High Order》的论文，后来被广泛称为"数值分析的第一篇现代论文"。从那时起，完全主元下的增长因子是个什么水平，就成了数值分析中悬而未决的核心问题。1961年，Wilkinson给出了一个拟多项式上界，大约是2·n^((log n)/4)左右，并顺嘴说了一句："目前还没见过增长因子超过8的矩阵。" 这句话后来催生了一个著名的猜想：完全主元下增长因子至多不超过n
这个猜想在数值分析界的地位，差不多相当于哥德巴赫猜想在数论里的感觉。但它后来被证伪了：首先在n=13的浮点计算中发现了反例[Gou91]，然后被Edelman严格化为精确算术下的反例[Ede92]。最近，Edelman和Urschel证明了对所有n≥11都存在增长超过n的常数倍的矩阵[EU24]。但真正的问题是：完全主元增长因子的渐近下界到底是什么量级？是多项式？还是拟多项式？这个问题一直没有人能回答。
这篇论文扔出了一颗重磅炸弹：完全主元增长因子的渐近下界不是多项式，而是拟多项式
更妙的是，论文还证明了存在一个"好"的随机行置换策略（体积主元），使得LU分解中L和U的Frobenius范数的期望都控制在O(n³)量级，从而在期望意义下增长因子不超过O(n²)：
从技术层面看，论文构造下界矩阵的核心工具是Sylvester-Hadamard矩阵。这类矩阵具有极强的递归结构，其元素按特定方式排列后，在完全主元消元过程中会不断产生新的"大元素"，最终导致拟多项式级别的增长。作者巧妙地利用了Hadamard矩阵的谱性质和张量积结构，将增长因子的下界问题转化为一个组合计数问题，从而得到了n^(Ω(log n))的结论。这种构造方法本身就是一个重要的技术贡献，为后续研究提供了新的工具箱。
具体来说，Sylvester-Hadamard矩阵H_k的维度为2^k×2^k，其元素为±1，且满足H_k = H_1 ⊗ H_{k-1}的递归关系。作者发现，当对这类矩阵进行适当的行置换后，完全主元消元过程中每一步的主元都恰好落在某个特定的子块上，而这些子块的行列式值呈现出规律性的增长。通过精确计算这些子块的行列式比值，作者能够证明增长因子至少为n^(c·log n)的形式。这种构造不仅优雅，而且具有高度的可验证性——读者可以手动验证小维度情形，从而建立对证明的信心。
稀疏矩阵的"陷阱"：部分主元的指数增长 这里有个流传很广的错觉：Wilkinson矩阵那种指数爆炸的例子，只会在精心构造的稠密矩阵里发生，真实工程中遇到的稀疏矩阵应该没事吧？
论文直接击碎了这个幻想。龙哥看到这部分结论的时候，表情大概是这样的：
此外，论文还指出：随机化部分主元同样不保险。对于任意参数p，都存在矩阵使得随机化部分主元以高概率产生e^(Ω_p(n/log n))的指数增长。这说明随机化并不能"洗掉"最坏情况——这在理论层面给"随机化=更安全"这种流行说法泼了一盆不小的冷水。不过，论文也证明了还存在另一种随机策略（体积主元），在期望意义下能达到多项式界。当然，这种策略的实现代价也更高，并不能完全替代部分主元。
从工程角度看，这个结果对稀疏直接求解器的设计有直接警示意义。现代稀疏LU分解中，常用的策略是先用图论方法做符号分解（symbolic factorization），确定非零元模式，然后再做数值分解。如果在数值分解阶段使用部分主元，那么即使矩阵本身非常稀疏，也可能遭遇指数级的元素增长。论文的构造表明，这种风险并非理论上的杞人忧天，而是真实存在的。因此，对于病态或接近病态的稀疏矩阵，采用更稳健的主元策略（如车房主元或阈值部分主元）仍然是必要的。
值得注意的是，论文中关于稀疏矩阵的构造非常精巧。以每行3个非零元的构造为例，其基本思想是将Wilkinson矩阵的稠密结构"压缩"到稀疏模式中，同时保留导致指数增长的关键特征。具体来说，作者将矩阵设计为带状结构，使得消元过程中每一步的主元都恰好落在某个特定的位置，从而复制了稠密情况下的增长模式。这种"稀疏化"技巧本身就是一个重要的方法论贡献，可能在其他数值算法的最坏情况分析中找到应用。
理论之美：数学证明如何重塑计算科学 这篇论文的意义，不只是一串定理和证明的堆积，而是对整个数值分析基础的一次深度刷新。很多年之后，当我们回看高斯消元的研究历史，这篇论文大概率会被标记为一个标志性的节点。
首先，它把一个从1940年代悬而未决的开放问题推进到了"基本尘埃落定"的状态。完全主元增长因子的渐近行为是拟多项式，这个结论不是修修补补的增量，而是一个定性的跃迁。任何数值分析教科书的未来版本，都会需要提到这个结果。对一代代学习数值计算的学生来说，"完全主元增长因子不超过n"这个曾经的美梦算是彻底醒透了，取而代之的是一个更复杂、也更真实的图景。
其次，论文在证明技巧上展现了惊人的丰富性：稀疏矩阵构造、Sylvester Hadamard矩阵下界、行列式点过程（DPP）耦合、NP困难性归约、随机矩阵的谱集中不等式……这些工具在数值分析论文中出现任何一个都算豪华，一篇论文全部用上，让人不得不感叹作者的数学储备相当雄厚。特别是用DPP来做体积主元的构造，这可能是第一次有人把DPP用于高斯消元主元选择——跨界又自然，给后来的研究者打开了一扇新窗。
第三，对工程实践的启示同样值得思考。虽然目前所有编程语言都不会因为这篇论文而改变默认的线性求解器，但对于那些正在设计新数值库、新硬件加速的稀疏直接解法器的人来说，论文中关于稀疏矩阵最坏情况的刻画是很有价值的参考——它提醒我们，在追求极致性能的同时，数值稳定性依然是一根不能放松的弦。
最后，回到最开始的那句话：高斯消元是世界上最古老的算法之一，而这篇论文证明它身上还有未被挖掘的深度。理论之美，不在于给出所有答案，而在于让未知变成已知、让猜想变成定理、让恐惧变成理解——这种踏实感，恐怕正是数学最迷人的地方。
从更广阔的视角看，这篇论文也体现了理论计算机科学与数值分析之间日益紧密的联系。NP难结果的引入、随机化算法的分析、组合构造的运用——这些方法论上的交叉融合，预示着未来数值算法研究将越来越多地借鉴理论计算机科学的工具和视角。对于年轻研究者来说，这无疑是一个令人振奋的信号：在看似成熟的领域，依然存在着根本性的开放问题等待解决。
龙迷三问 这篇论文到底在解决什么问题？ 约翰·厄舍尔（John Urschel）等人的新论文证明了完全主元与车房主元下高斯消元增长因子为维度拟多项式，终结了八十余年开放猜想之争；同时揭示部分主元在稀疏矩阵下仍可能指数增长，随机化主元同样不稳定，最优行置换求取为NP难问题这篇工作最值得看的点是什么？ 本文为纯理论数学论文，没有实验部分。主要成果是证明了多个关于高斯消元增长因子的定理，包括：部分主元下稀疏矩阵的指数增长（定理1.1）、低增长行交换的存在性（定理1.2）、所有主元策略的下界（定理1.3）、最小化增长因子的NP难度（定理1.4）、随机化部分主元的大增长（定理1.5）、rook主元的拟多项式增长（定理1.6）和完全主元的拟多项式增长（定理1.7）。这篇工作的边界或风险在哪里？ 优点：1）解决了数值分析领域多个长期开放问题，特别是完全主元增长因子的渐近行为；2）理论证明严谨，覆盖了多种主元策略；3）结果具有重要的理论意义，对理解高斯消元的数值稳定性有深远影响。缺点：1）纯理论论文，缺乏实验验证；2）部分证明依赖于随机矩阵和概率方法，构造的矩阵可能在实际计算中不常见；3）论文写作质量有待提高，作者在文中也承认了这一点。如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~
龙哥点评 论文创新性分数： ★★★★☆
本文通过构造特定矩阵族，利用随机正交矩阵、Hadamard矩阵和稀疏矩阵等工具，从理论上严格证明了高斯消元在不同主元策略下增长因子的渐近行为，包括完全主元和rook主元的拟多项式下界、部分主元对稀疏矩阵的指数增长、以及随机化部分主元的不稳定。实验合理度： ★★★☆☆
现有材料未完整覆盖数据划分、基线公平性和统计显著性，因此按中性评价处理。学术研究价值： ★★★★☆
本文通过构造特定矩阵族，利用随机正交矩阵、Hadamard矩阵和稀疏矩阵等工具，从理论上严格证明了高斯消元在不同主元策略下增长因子的渐近行为，包括完全主元和rook主元的拟多项式下界、部分主元对稀疏矩。稳定性： ★★★☆☆
现有材料未提供充分的极端条件、重复运行或扰动测试，稳定性暂按中性评价。适应性以及泛化能力： ★★★☆☆
现有材料未完整展示跨数据集、跨场景或分布外实验，泛化能力仍需进一步验证。硬件需求及成本： ★★★☆☆
现有材料缺少完整训练资源、参数量、显存和推理时延信息，成本暂按中性评价。复现难度： ★★★☆☆
现有材料未确认完整代码、配置、数据处理脚本和权重是否齐备，复现难度暂按中性评价。产品化成熟度： ★★★☆☆
论文验证以研究实验为主，真实部署中的时延、成本、维护和异常场景仍需补充验证。可能的问题： ，特别是完全主元增长因子的渐近行为；2）理论证明严谨，覆盖了多种主元策略；3）结果具有重要的理论意义，对理解高斯消元的数值稳定性有深远影响。缺点：1）纯理论论文，缺乏实验验证；2）部分证明依赖于随机矩阵和概率方法，构造的矩阵可能在实际计算中不常见；3）论文写作质量有待提高，作者在文中也承认了这一点。
主要参考文献
[1] Rikhav Shah, John Urschel. Entry Growth in Gaussian Elimination. arXiv:2608.19189v2. [2] J. von Neumann, H. H. Goldstine. Numerical inverting of matrices of high order. 1947. [3] J. H. Wilkinson. The Algebraic Eigenvalue Problem. 1965. [4] N. J. Higham. Accuracy and Stability of Numerical Algorithms. 2002. [5] L. V. Foster. The growth factor and efficiency of Gaussian elimination with rook pivoting. 1997. [6] A. Edelman, J. Urschel. Growth factors of Hadamard matrices and the pivot conjecture. 2024. [7] A. Bisain, A. Edelman, J. Urschel. Complete pivoting growth in Gaussian elimination. 2025. *本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～ 想了解更多原文细节的小伙伴，可以点击 "阅读原文"， 查看更多原论文细节哦！
