Data Structures Algorithms 简明教程
Strassen’s Matrix Multiplication
Strassen 矩阵乘法是求解矩阵乘法问题的一种分治法。通常的矩阵乘法方法以每个行为每一列相乘来得到结果矩阵。这种方法的时间复杂度为 O(n3) ，因为它需要两个循环才能完成乘法。Strassen 方法被引入以将时间复杂度从 O(n3) 降低到 O(nlog 7) 。
Strassen’s Matrix Multiplication is the divide and conquer approach to solve the matrix multiplication problems. The usual matrix multiplication method multiplies each row with each column to achieve the product matrix. The time complexity taken by this approach is O(n3), since it takes two loops to multiply. Strassen’s method was introduced to reduce the time complexity from O(n3) to O(nlog 7).
Naive Method
首先，我们将讨论朴素方法及其复杂性。此处，我们正在计算 Z=XYY。使用朴素方法，如果这些矩阵的顺序为 p × q 和 q × r ，则可以将两个矩阵（ X 和 Y ）相乘，并且结果矩阵的顺序为 p × r 。以下伪代码描述了朴素乘法 −
First, we will discuss Naive method and its complexity. Here, we are calculating Z=𝑿X × Y. Using Naive method, two matrices (X and Y) can be multiplied if the order of these matrices are p × q and q × r and the resultant matrix will be of order p × r. The following pseudocode describes the Naive multiplication −
Algorithm: Matrix-Multiplication (X, Y, Z)
for i = 1 to p do
for j = 1 to r do
Z[i,j] := 0
for k = 1 to q do
Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]Strassen’s Matrix Multiplication Algorithm
在此背景下，使用 Strassen 矩阵乘法算法可以稍微提高时间消耗。
In this context, using Strassen’s Matrix multiplication algorithm, the time consumption can be improved a little bit.
Strassen 矩阵乘法只能执行 square matrices ，其中 n 为 power of 2 。两个矩阵的顺序为 n × n 。
Strassen’s Matrix multiplication can be performed only on square matrices where n is a power of 2. Order of both of the matrices are n × n.
将 X 、 Y 和 Z 划分为四个 (n/2)×(n/2) 矩阵，如下所示 −
Divide X, Y and Z into four (n/2)×(n/2) matrices as represented below −
$Z = \begin{bmatrix}I & J \\K & L \end{bmatrix}$ $X = \begin{bmatrix}A & B \\C & D \end{bmatrix}$ 和 $Y = \begin{bmatrix}E & F \\G & H \end{bmatrix}$
$Z = \begin{bmatrix}I & J \\K & L \end{bmatrix}$ $X = \begin{bmatrix}A & B \\C & D \end{bmatrix}$ and $Y = \begin{bmatrix}E & F \\G & H \end{bmatrix}$
使用 Strassen 算法计算以下结果 −
Using Strassen’s Algorithm compute the following −
M_{1} \: \colon= (A+C) \times (E+F)
M_{2} \: \colon= (B+D) \times (G+H)
M_{3} \: \colon= (A-D) \times (E+H)
M_{4} \: \colon= A \times (F-H)
M_{5} \: \colon= (C+D) \times (E)
M_{6} \: \colon= (A+B) \times (H)
M_{7} \: \colon= D \times (G-E)
然后，
Then,
I \: \colon= M_{2} + M_{3} - M_{6} - M_{7}
J \: \冒号= M_{4} + M_{6}
J \: \colon= M_{4} + M_{6}
K \: \冒号= M_{5} + M_{7}
K \: \colon= M_{5} + M_{7}
L \: \冒号= M_{1} - M_{3} - M_{4} - M_{5}
L \: \colon= M_{1} - M_{3} - M_{4} - M_{5}
Analysis
T(n)=\begin{cases}c & 如果\:n= 1\\7\:x\:T(\frac{n}{2})+d\:x\:n^2 & 其他\end{cases} \:其中\: c\:和 \:d\:为常数
T(n)=\begin{cases}c & if\:n= 1\\7\:x\:T(\frac{n}{2})+d\:x\:n^2 & otherwise\end{cases} \:where\: c\: and \:d\:are\: constants
使用此递推关系，我们获得 T(n) = O(n^{log7})
Using this recurrence relation, we get $T(n) = O(n^{log7})$
因此，Strassen 矩阵乘法算法的复杂度为 O(n^{log7})。
Hence, the complexity of Strassen’s matrix multiplication algorithm is $O(n^{log7})$.