Strassen 公式

下载 Wolfram 笔记本

执行矩阵乘法通常所需的标量运算数（即，加法和乘法的总数）是

(1)

（即，次乘法和次加法）。然而，Strassen (1969) 发现了如何用

(2)

次标量运算来乘两个矩阵，其中是以 2 为底的对数，这小于，当时。对于为 2 的幂次方 ()，(2) 的两部分可以写成

			(3)
			(4)
			(5)
			(6)
			(7)
			(8)
			(9)
			(10)
			(11)
			(12)

因此 (◇) 变为

(13)

对于 2 的幂次方，Strassen 算法的领先指数因此为。

下表总结了 Coppersmith 和 Winograd (1990) 的构造在次幂的领先指数中已证明的极限的改进（参见 Le Gall 2014，表 I）。

	上限	参考文献
1	2.3871900	Coppersmith 和 Winograd (1990)
2	2.3754770	Coppersmith 和 Winograd (1990)
4	2.3736898	Strothers (2010), Davie 和 Strothers (2013)
4	2.3729269	Vassilevska Williams (2012)
8	2.3729	Vassilevska Williams (2014)
8	2.3728642	Le Gall (2014)
16	2.3728640	Le Gall (2014)
32	2.3728639	Le Gall (2014)

使用 Strassen 乘法，矩阵可以相乘

(14)

(15)

仅需

(16)

次标量运算（结果表明，其中七次是乘法，18 次是加法）。定义七个乘积（总共涉及 10 次加法）为

			(17)
			(18)
			(19)
			(20)
			(21)
			(22)
			(23)

然后，使用剩余的八次加法，矩阵乘积给出为

			(24)
			(25)
			(26)
			(27)

（Strassen 1969, Press et al. 1989）。

一个矩阵的矩阵求逆以产生也可以用比预期更少的操作完成，使用以下公式

			(28)
			(29)
			(30)
			(31)
			(32)
			(33)
			(34)
			(35)
			(36)
			(37)
			(38)

（Strassen 1969, Press et al. 1989）。

不幸的是，Strassen 算法的数值表现不佳。它只是弱稳定，即，计算结果满足不等式

(39)

其中是单位舍入误差，而相应的强稳定性不等式（通过用矩阵元素的绝对值替换矩阵范数获得）不成立。

另请参阅

复数乘法, Karatsuba 乘法

使用 Wolfram|Alpha 探索

更多尝试

参考文献

Coppersmith, D. 和 Winograd, S. "Matrix Multiplication via Arithmetic Programming." J. Symb. Comput. 9, 251-280, 1990.Davie, A. M.; 和 Strothers, A. J. "Improved Bound for Complexity of Matrix Multiplication." Proc. Royal Soc. Edinburgh 143A, 351-370, 2013.Douglas, C.; Heroux, M.; Slishman, G.; 和 Smith, R. "GEMMW: A Portable Level 3 BLAS Winograd Variant of Strassen's Matrix-Matrix Multiply Algorithm." J. Comput. Phys. 110, 1-10, 1994.Le Gall, F. "Powers of Tensors and Fast Matrix Multiplication." 2014 年 1 月 30 日. https://arxiv.org/abs/1401.7714.Pan, V. How to Multiply Matrices Faster. New York: Springer-Verlag, 1982.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; 和 Vetterling, W. T. "Is Matrix Inversion an

Process?" §2.11 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 95-98, 1989.Strassen, V. "Gaussian Elimination is Not Optimal." Numerische Mathematik 13, 354-356, 1969.Strothers, A. "On the Complexity of Matrix Multiplication." Ph.D. 论文. Edinburgh, Scottland: University of Edinburgh, 2010.Vassilevska Williams, V. "Multiplying Matrices Faster Than Coppersmith-Winograd." In STOC'12--Proceedings of the 2012 ACM Symposium on Theory of Computing. New York: ACM, pp. 887-898, 2012.Vassilevska Williams, V. "Multiplying Matrices in