Strassen矩阵相乘算法

C语言

Posted by HT on December 20, 2017

基于分治策略和一些处理技巧,Strassen算法的流程如下:

  1. 两个矩阵A B相乘时,将A, B, C分成相等大小的方块矩阵:
  2. 可以看出C是这么得来的:
  3. 现在定义7个新矩阵:
  4. 而最后的结果矩阵C 可以通过组合上述7个新矩阵得到: 如此,通过递归算法,可将N阶矩阵化为二阶矩阵相称。

Strassen算法比通用矩阵相乘算法好一点,因为通用矩阵相乘算法时间复杂度是 ,而Strassen算法复杂度只是 。但随着n的变大, Strassen算法是比通用矩阵相乘算法变得更有效率。

最后附上GitHub:https://github.com/zht1999/Stressen