此条目或其章节极大或完全地依赖于某个单一的来源。 (2014年9月3日) 请协助补充多方面可靠来源以改善这篇条目。 致使用者:请搜索一下条目的标题(来源搜索:"施特拉森算法" — 网页、新闻、书籍、学术、图像),以检查网络上是否存在该主题的更多可靠来源(判定指引) |
施特拉森算法(英语:Strassen algorithm)是一个计算矩阵乘法的算法,时间复杂度为。
简介
施特拉森算法在1969年由沃尔克·施特拉森所提出,是第一个时间复杂度低于 的矩阵乘法算法。由于算法简单理解,且为第一个被提出来的特性,常被算法教材拿来当作主定理(英语:Master theorem)计算时间复杂度的例子。
另外,因为施特拉森算法证明了矩阵乘法存在时间复杂度低于 的算法,使得更多学者投入研究,寻找更快的算法。
算法
定义
设 、 为域 上的方矩阵。求两者的积 。一般矩阵可以填0的方法计算令它成为 矩阵。
-
计算
将A, B, C分成相等大小的方块矩阵:
-
即
-
于是
-
-
-
-
引入新矩阵
-
-
-
-
-
-
-
可得:
-
-
-
-
其中 的计算也是使用施特拉森算法求得。
评论
一般矩阵乘法的时间复杂度为 ,施特拉森算法因为只有每次的分治法(英语:Divide and conquer algorithm)只有七个矩阵乘法运算,所以依照主定理(英语:Master theorem)可以得出时间复杂度为 。但Strassen算法的数值稳定性较差。
现时时间复杂度最低的矩阵乘法算法是Coppersmith-Winograd方法的一种扩展方法,其算法复杂度为 )。[1]
相关连结
参考来源