用Strassen算法(分治)计算矩阵乘法及python实现(一)

前言:

设A和B都是n*n的矩阵,那么我们可以很容易通过一个简单的分治算法得到乘积C=A·B,以下是其伪代码,它将接收n*n矩阵A,B,并返回它们的乘积C:

SQUARE-MATRIX-MULLTIPLY(A,B)
n=A.rows
let C be a new n*n matrix
for i=1 to n
     for j=1 to n
         c[i][j]=0
         for k=1 to n
               c[i][j]=c[i][j]+a[i][k]*b[k][j]

return C

显然三重循环中每一重都要执行n布,因此其时间复杂度为O(n^3),而Strassen算法的时间复杂度为O(n^log7),显然Strassen算法更优。

Strassen算法的核心思想是通过常数次的额外的矩阵加法来减少递归的次数,如果你对递归有所了解,那么你应该明白这种代价确实能够减少渐进运行时间。下面来介绍一下Strassen算法的步骤

Strassen算法的步骤

为简单起见,当使用分治算法计算矩阵积C=A*B时,假定三个矩阵均为n*n矩阵,其中n为2的幂。我们做出这个假设是因为在每个分解步骤中,n*n矩阵都被划分为4个n/2*n/2的子矩阵,如果假定n是2的幂,则只要n>=2即可保证子矩阵规模n/2为整数。

Strassen算法一共4个步骤:

  1. 将输入矩阵A、B和输出矩阵C分解为n/2*n/2的子矩阵。采用下标计算方法,此步骤花费O(1)时间。
  2. 创建10个n/2*n/2的矩阵S1, S2, … , S10,每个矩阵保存步骤1中创建的两个子矩阵的和或差。花费时间为O(n^2)。
  3. 用步骤1中创建的子矩阵和步骤2中创建的10个矩阵,递归地计算7个矩阵积P1, P2, …, P7。每个矩阵Pi都是n/2*n/2的。
  4. 通过Pi矩阵的不同组合进行加减计算,计算出结果矩阵C的子矩阵C11, C12, C21, C22。花费时间O(n^2)。

以上即为Strassen算法的简略步骤,至于具体步骤,敬请期待 用Strassen算法(分治)计算矩阵乘法及python实现(二)。