施特拉森演算法

维基百科,自由的百科全书
跳转至: 导航搜索

Strassen演算法是個計算矩陣乘法演算法


A, B F上的方矩陣。求兩者的積C

(一般矩陣可以填0的方法計算令它成為矩陣。)

A, B, C分成相等大小的方塊矩陣:

於是

引入新矩陣

可得:

其中M_{i,j}的計算也是使用Strassen演算法求得。

評論[编辑]

一般矩陣乘法的時間複雜度為,Strassen演算法則是。但Strassen演算法的數值穩定性較差。

現時時間複雜度最低的矩陣乘法演算法是Coppersmith-Winograd方法的一种扩展方法,其算法复杂度为O(n2.3727)[1]

参考来源[编辑]

  1. ^ Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd (PDF). 而1990年Coppersmith-Winograd方法提出时的算法复杂度为。O(n2.376)