计算机科学

首页 > 计算机科学

施特拉森算法

2018-07-27 10:04:57     所属分类:算法

施特拉森算法英语:Strassen algorithm)是一个计算矩阵乘法的算法,时间复杂度为

目录

  • 1 简介
  • 2 算法
    • 2.1 定义
    • 2.2 计算
  • 3 评论
  • 4 相关连结
  • 5 参考来源

简介

矩阵乘法算法的演进。

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

另外,因为施特拉森算法证明了矩阵乘法存在时间复杂度低于的算法,使得更多学者投入研究,寻找更快的算法。

算法

定义

为域上的方矩阵。求两者的积。一般矩阵可以填0的方法计算令它成为矩阵。

计算

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

于是

引入新矩阵

可得:

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

评论

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

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

相关连结

  • 矩阵乘法

参考来源

  1. ^ Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd (PDF). 而1990年Coppersmith-Winograd方法提出时的算法复杂度为
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/338743.html

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
支付宝扫一扫赏金或者微信支付5毛钱,阅读全文

打开微信扫一扫,即可进行阅读全文哦


相关推荐