矩阵乘法需要O(n^3)的时间，不能再减少

牛津大学计算中心主任、英国皇家学会院士、美国工业与应用数学会（SIAM）主席Nick Trfethen 教授2012年11月的《SIAM News》上撰文链接内容以短小篇幅简明地阐述了数值线性代数方向两个未解之谜：1. 如何快速求逆矩阵 2. 高斯消元法在实际应用中的稳定性。

第一个问题的原文如下：

The first problem is, can an n × n linear system of equations Ax = b be solved in O(n2+ε) operations, where ε is arbitrarily small? In other words, could there be a “fast matrix inverse,” like the fast Fourier transform?

实际上，矩阵乘法的计算复杂性下限问题早就被我国学者解决。本人的看法如下：

对于两个n阶方阵，假如所有这些元素之间是“相互独立”的，则定义所包含的n个乘法的结果也是“相互独立”的。即n3的乘法是必须的。由于加法形成lgn 的进位位，“相互独立元素”的方阵乘法，必须的信息量是O(n^3×lgn)。换言之，随机有理方阵乘法的信息量下界：O(n^3×lgn)，不存在比它更小的精确计算方法。

现有所谓O(n2+ε)的矩阵乘法，都是以降低计算精度（误差增大）为代价的。这些复杂性降低的核心技术：把多个乘法合并在一起计算。对于有限位数的数字计算机，这必然导致误差的增大。

1990年陈道琦、谢友才、应文隆在科学通报发表的《关于矩阵乘法的一个最佳算法》，只用一次乘法。该文对我的发现具有直接的启发。

参考文献：

[1] Nick Trefethen. The Smart Money’s on Numerical Analysts [J]. SIAM News, Volume 45, Number 9, November 2012.

[2] 美国SIAM主席、皇家学会院士提的两个数值代数问题（1）[EB/OL]. http://www.mysanco.com/wenda/index.php?class=discuss&action=question_item&questionid=1097

[3] 陈道琦，谢友才，应文隆. 关于矩阵乘法的一个最佳算法[J]. 科学通报, 1990, 35(3 ): 161-161.

后记：

(1) 听说“矩阵乘法”和“矩阵求逆”不是一个问题，还真不清楚是怎么回事。高斯消元法？克莱姆？逆矩阵？还有别的吗？“2. 高斯消元法在实际应用中的稳定性”和“矩阵求逆”的关系是什么？

(2) “高斯消元法在实际应用中的稳定性”应该是除法里分母的绝对值比0明显大。数值计算稳定性的核心成因包括：（1）计算使用有限的字长（有效数字位数），（2）除法里分母接近0（涉及矩阵时表现为矩阵的奇异性）。小绝对值的分母（特别是无理数分母）导致较大（亦即较长）的分式计算结果。当有效数字位数有限时，造成截断位数引起的误差，这是数值计算不稳定的核心原因。一般加法、减法的结果的有效数字位数变化慢（相对于乘法、除法），所以乘法、除法计算引起的有效数字位数的快速增加（结合有限的有效数字位数计算），造成了数值计算的不稳定性。

(3) 当然，这并不是说所有的数值计算稳定性都来源于“有效数字位数”的丢失。至少目前不能肯定这点（有效数字位数的丢失）。

______________ 相关资料 ______________

Weisstein, Eric W. "Strassen Formulas." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/StrassenFormulas.html

Unfortunately, Strassen's algorithm is not numerically well-behaved. It is only weakly stable, i.e., the computed result  satisfies the inequality

where u  is the unit roundoff error, while the corresponding strong stability inequality (obtained by replacing matrix norms with absolute values of the matrix elements) does not hold.

相关链接：
[1] 俗解Chaitin定理
http://bbs.sciencenet.cn/home.php?mod=space&uid=107667&do=blog&id=478066

[2] 数学证明的长度：与公理系统能力负相关
http://bbs.sciencenet.cn/blog-107667-729907.html