姓名：张昊楠
学号：21021210691
学院：电子工程学院
【嵌牛导读】介绍strssen算法的基本原理与实现方法
【嵌牛鼻子】矩阵相乘 strassen算法
机器学习中需要训练大量数据，涉及大量复杂运算，例如卷积、矩阵等。这些复杂运算不仅多，而且每次计算的数据量很大，如果能针对这些运算进行优化，可以大幅提高性能。
常规的矩阵相乘算法，其时间复杂度为,本文介绍的strassen算法，能够降低算法的时间复杂度，对于大规模的矩阵运算有很大帮助。
本文转载自：算法导论-矩阵乘法-strassen算法
1、矩阵相乘的朴素算法 T(n) = Θ(n3)
朴素矩阵相乘算法，思想明了，编程实现简单。时间复杂度是Θ(n^3)。伪码如下
for i = 1 to n
do for j = 1 to n
do c[i][j] = 0
for k = 1 to n
do c[i][j] = c[i][j] + a[i][k]+ b[k][j]
2、矩阵相乘的strassen算法 
(x^2.81)
矩阵乘法中采用分治法，第一感觉上应该能够有效的提高算法的效率。如下图所示分治法方案，以及对该算法的效率分析。有图可知，算法效率是Θ(n^3)。算法效率并没有提高。下面介绍下矩阵分治法思想：
鉴于上面的分治法方案无法有效提高算法的效率，要想提高算法效率，由主定理方法可知必须想办法将2中递归式中的系数8减少。Strassen提出了一种将系数减少到7的分治法方案，
效率分析如下：
3、性能分析
可以发现：可以看到使用Strassen算法时，耗时不但没有减少，反而剧烈增多，在n=512时计算时间就无法忍受，效果没有朴素矩阵算法好。网上查阅资料，现罗列如下：
1）采用Strassen算法作递归运算，需要创建大量的动态二维数组，其中分配堆内存空间将占用大量计算时间，从而掩盖了Strassen算法的优势
2）于是对Strassen算法做出改进，设定一个界限。当n<界限时，使用普通法计算矩阵，而不继续分治递归。需要合理设置界限，不同环境（硬件配置）下界限不同
3）矩阵乘法一般意义上还是选择的是朴素的方法，只有当矩阵变稠密，而且矩阵的阶数很大时，才会考虑使用Strassen算法。
分析原因：（网上总结的说法）http://blog.csdn.net/handawnc/article/details/7987107
仔细研究后发现，采用Strassen算法作递归运算，需要创建大量的动态二维数组，其中分配堆内存空间将占用大量计算时间，从而掩盖了Strassen算法的优势。于是对Strassen算法做出改进，设定一个界限。当n<界限时，使用普通法计算矩阵，而不继续分治递归。
改进后算法优势明显，就算时间大幅下降。之后，针对不同大小的界限进行试验。在初步试验中发现，当数据规模小于1000时，下界S法的差别不大，规模大于1000以后，n取值越大，消耗时间下降。最优的界限值在32～128之间。
因为计算机每次运算时的系统环境不同（CPU占用、内存占用等），所以计算出的时间会有一定浮动。虽然这样，试验结果已经能得出结论Strassen算法比常规法优势明显。使用下界法改进后，在分治效率和动态分配内存间取舍，针对不同的数据规模稍加试验可以得到一个最优的界限。http://www.cppblog.com/sosi/archive/2010/08/30/125259.html
时间复杂度就马上降下来了。。但是不要过于乐观。
从实用的观点看，Strassen算法通常不是矩阵乘法所选择的方法：
1 在Strassen算法的运行时间中，隐含的常数因子比简单的O(n^3)方法常数因子大
2 当矩阵是稀疏的时候，为稀疏矩阵设计的算法更快
3 Strassen算法不像简单方法那样子具有数值稳定性
4 在递归层次中生成的子矩阵要消耗空间。
所以矩阵乘法一般意义上还是选择的是朴素的方法，只有当矩阵变稠密，而且矩阵的阶数>20左右，才会考虑使用Strassen算法。
4、参考资料
【1】http://blog.csdn.net/xyd0512/article/details/8220506
【2】http://blog.csdn.net/zhuangxiaobin/article/details/36476769
【3】http://blog.csdn.net/handawnc/article/details/7987107
