矩阵乘法及求解递归式

Posted on

Matrix multiply

算法形式

矩阵乘法规则:$c_{ij}=\sum\limits_{k=1}^na_{ik}b_{kj}$
最简单算法的伪代码:

1
2
3
4
5
6
7
Matrix-Multiply(A,B)
n = A.lows
for i = 1 to n
	for j = 1 to n 
		c_ij=0
		for k = 1 to n
			c_ij = c_ij + a_ik*b_kj

第一个for循环计算每一行的元素，第二个for循环计算每一列中的每一个元素，第三个for循环迭代计算求和，三重for循环都要执行n步，因此需要$\Theta(n^3)$时间
如果采用分治策略，即使用分块矩阵做乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Matrix-Multiply-Recursive(A,B)
n = A.lows
if n == 1
	c11=a11*b11
else partition A,B 
	c11 = Matrix-Multiply-Recursive(A11,B11)
		+ Matrix-Multiply-Recursive(A12,B21)
	c12 = Matrix-Multiply-Recursive(A11,B12)
		+ Matrix-Multiply-Recursive(A12,B22)
	c21 = Matrix-Multiply-Recursive(A21,B11)
	 	+ Matrix-Multiply-Recursive(A22,B21)
	c22 = Matrix-Multiply-Recursive(A21,B12)
		+ Matrix-Multiply-Recursive(A22,B22)
return c

虽然该算法要分解矩阵，但我们可以利用下标在$\Theta(1)$时间内完成，对总时间无影响，而每次加法时间为$\Theta(n^2)$,最终的递归式为$T(n)=8T(n/2)+\Theta(n^2)$,得到的结果依然为$T(n)=\Theta(n^3)$，没有改进
Strassen算法的核心思想是令递归树稍微不那么茂盛，即只递归7次，而不是8次

算法分析（求解递归式）

  • 代入法求解
  • 递归树求解
  • 主方法求解

源代码

习题解答

算法改进