版权归原作者所有,如有侵权,请联系我们

[科普中国]-施特拉森算法

科学百科
原创
科学百科为用户提供权威科普内容,打造知识科普阵地
收藏

施特拉森算法(英语:Strassen algorithm)是一个计算矩阵乘法的算法。

简介矩阵乘法算法的演进。

施特拉森算法在1969年由Volker Strassen提出来,是第一个时间复杂度低于{\displaystyle O(n^{3})}的矩阵乘法算法。由于算法简单理解,且为第一个被提出来的特性,常被算法教材拿来当作主定理(英语:Master theorem)计算时间复杂度的例子。

另外,因为施特拉森算法证明了矩阵乘法存在时间复杂度低于{\displaystyle O(n^{3})}的算法,使得更多学者投入研究,寻找更快的算法。1

算法定义设A、B为域F上的方矩阵。求两者的积{\displaystyle C}。一般矩阵可以填0的方法计算令它成为矩阵。

计算将A,B,C分成相等大小的方块矩阵:

于是

引入新矩阵

可得:

其中的计算也是使用施特拉森算法求得。

评论一般矩阵乘法的时间复杂度为,施特拉森算法因为只有每次的分治法(英语:Divide and conquer algorithm)只有七个矩阵乘法运算,所以依照主定理(英语:Master theorem)可以得出时间复杂度为。但Strassen算法的数值稳定性较差。

现时时间复杂度最低的矩阵乘法算法是Coppersmith-Winograd方法的一种扩展方法,其算法复杂度为)。1

本词条内容贡献者为:

程鹏 - 副教授 - 西南大学