矩阵乘法的Strassen算法

矩阵乘法计算规则，第一个矩阵第一行的每个数字（2和1），各自乘以第二个矩阵第一列对应位置的数字（1和1），然后将乘积相加（ 2 x 1 + 1 x 1）

普通算法：将耗费 n3 ..

SQUARE-MATRIX-MULTIPLY(A, B)

n=A.rows

let C be a new n*n matrix

for i = 1 to n

for j = 1 to n

Cij = 0;

for k = 1 to n

Cij = Cij + Aik*Bkj

return C

直接的递归分治算法：T(n) = 8*T(n/2) + O(n2)

每次矩阵的加法花费O(n2)的时间

SQUARE-MATRIX-RECURSIVE(A, B)

n=A.rows let C be a new n*n matrix

if n==1

c11 = a11 * b11

else partition A,B and C

C11 = self(a11,b11) + self(a12,b21)

C12 = self(a11,b12) + self(a12,b22)

C21 = self(a21,b11) + self(a22,b21)

C22 = self(a21,b12) + self(a22,b22)

return C

strassen算法的核心是令递归树，稍微不那么茂盛一点，把8次递归减少到7次，8次n/2*n/2 减少到7次

第1步：partition，将A,B,C均分解为四个n/2 * n/2的子矩阵。

A11, A12,

A21,A22

B11,B12,

B21,B22

C11,C12,

C21,C22

C = A*B可以改写为

C11 C12 = A11 A12 * B11 B12

C21 C22 A21 A22 B21 B22

第2步：创建10个n/2 * n/2的子矩阵，每个矩阵保存步骤1中创建的两个子矩阵的和或差，花费时间为O(n2)

S1 = B12 - B22

S2 = A11 + A12

S3 = A21 +A22

S4 = B21 - B11

S5 = A11 +A22

S6 = B11+B22

S7 = A12-A22

S8 = B21 + B22

S9 = A11-A21

S10 = B11+B12

第3步：递归地计算7次n/2 * n/2的矩阵

P1 = A11*S1 = A11*B12 - A11*B22

P2 = S2*B22 = A11*B22 + A12*B22

P3 = S3*B11 = A21*B11 + A22*B11

P4 = A22 * S4=A22*B21 - A22*B11

P5 = S5 * S6 = A11*B11 + A11*B22 + A22*B21 + A22*B22

P6 = S7 * S8 = A12*B21 + A12*B22 - A22*B21 - A22* B22

P7 = S9 * S10 = A11*B11 + A11*B12 -A21*B11 - A21*B12

C11 = P5 + P4 - P2 + P6

C12 = P1 + P2

C21 = P3 + P4

C22 = P5+P1-P3-P7

T(n) = 7T(n/2) + O(n2)

计算出复杂度为 O(nlg7)