无聊的矩阵乘法

偶然在《数据结构和算法分析上》看到了矩阵乘法的优化方法,长期以来人们认为矩阵乘法是需要n的3次方时间的,但在20世纪60年代末Strassen打破了3的屏障。不知道为什么看到下面这段话好有感触。

往常一样,有些细节需要考虑,如当N不是2的幂时的情况,不过还是有些根本性小缺憾。 Strassen算法在N不够大时不如矩阵直接相乘。它也不能推广到矩阵是稀疏(即含有许多的0元素)的情况,而且它还不容易并行化。当用浮点数运算时,在数值上它不如经典的算法稳定。因此,它只有有限的适用性。然而,它象征着重要理论的里程碑并证明了,在计算机科学像在许多其他领域一样,即使一个问题看似具有固有的复杂性,但在被证明以前却始终不可定论。

这个算法的时间复杂度是n的2.807355次方,最新的Coppersmith–Winograd算法一开始是n的2.375477次方,2010年改进到2.374,2011年改进到2.3728642 ,2012年改进的2.3728639。这数字好精益求精。( ̄▽ ̄)”

附上维基,参考链接2有惊喜

1 2

2 1

上面这个矩阵的值是0

1 2 3

2 3 1

3 1 2

上面这个矩阵的值是-18

这样一直算下去,f1 = 0,f2 = 0,f3 = -18,f4 = -208..
0
-18
-208
-3825
-59584

不知道数列网站OEIS上有这数列没

Leave a Reply