Strassen 矩阵乘法是一种分治法用于解决矩阵乘法问题。传统的矩阵乘法方法将每一行与每一列相乘以得到乘积矩阵。这种方法的时间复杂度为O(n3)因为需要两个循环进行乘法运算。Strassen 方法的引入将时间复杂度从O(n3)降低到O(nlog 7)。朴素方法首先我们讨论朴素方法及其复杂度。这里我们计算 Z X × Y。使用朴素方法两个矩阵X和Y可以相乘前提是它们的阶分别为p×q和q×r结果矩阵的阶为p×r。以下伪代码描述了朴素乘法——算法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]复杂度这里我们假设整数运算耗时O(1)。该算法中有三个for循环其中一个嵌套在另一个内部。因此该算法执行时间为O(n3)。Strassen 矩阵乘法算法在这种情况下使用 Strassen 矩阵乘法算法可以略微改善时间消耗。Strassen 矩阵乘法仅适用于方阵且n是2 的幂。两个矩阵的阶均为n × n。将X、Y和Z分为四个(n/2)×(n/2)子矩阵如下所示——$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}$使用 Strassen 算法计算以下内容——$$M_{1} \: \colon (AC) \times (EF)$$$$M_{2} \: \colon (BD) \times (GH)$$$$M_{3} \: \colon (A-D) \times (EH)$$$$M_{4} \: \colon A \times (F-H)$$$$M_{5} \: \colon (CD) \times (E)$$$$M_{6} \: \colon (AB) \times (H)$$$$M_{7} \: \colon D \times (G-E)$$然后$$I \: \colon M_{2} M_{3} - M_{6} - M_{7}$$$$J \: \colon M_{4} M_{6}$$$$K \: \colon M_{5} M_{7}$$$$L \: \colon M_{1} - M_{3} - M_{4} - M_{5}$$分析$$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})$因此Strassen 矩阵乘法算法的复杂度为 $O(n^{log7})$。示例让我们来看看 Strassens Matrix Multiplication 在各种编程语言中的实现C、C、Java、Python。C C Java Python#includestdio.h int main(){ int z[2][2]; int i, j; int m1, m2, m3, m4 , m5, m6, m7; int x[2][2] { {12, 34}, {22, 10} }; int y[2][2] { {3, 4}, {2, 1} }; printf(第一个矩阵是 ); for(i 0; i 2; i) { printf(\n); for(j 0; j 2; j) printf(%d\t, x[i][j]); } printf(\n第二个矩阵是 ); for(i 0; i 2; i) { printf(\n); for(j 0; j 2; j) printf(%d\t, y[i][j]); } m1 (x[0][0] x[1][1]) * (y[0][0] y[1][1]); m2 (x[1][0] x[1][1]) * y[0][0]; m3 x[0][0] * (y[0][1] - y[1][1]); m4 x[1][1] * (y[1][0] - y[0][0]); m5 (x[0][0] x[0][1]) * y[1][1]; m6 (x[1][0] - x[0][0]) * (y[0][0]y[0][1]); m7 (x[0][1] - x[1][1]) * (y[1][0]y[1][1]); z[0][0] m1 m4- m5 m7; z[0][1] m3 m5; z[1][0] m2 m4; z[1][1] m1 - m2 m3 m6; printf(\n使用 Strassen 算法得到的乘积 ); for(i 0; i 2 ; i) { printf(\n); for(j 0; j 2; j) printf(%d\t, z[i][j]); } return 0; }输出The first matrix is: 12 34 22 10 The second matrix is: 3 4 2 1 Product achieved using Strassens algorithm: 104 82 86 98#includeiostream using namespace std; int main() { int z[2][2]; int i, j; int m1, m2, m3, m4 , m5, m6, m7; int x[2][2] { {12, 34}, {22, 10} }; int y[2][2] { {3, 4}, {2, 1} }; cout第一个矩阵是 ; for(i 0; i 2; i) { coutendl; for(j 0; j 2; j) coutx[i][j] ; } cout\n第二个矩阵是 ; for(i 0;i 2; i){ coutendl; for(j 0;j 2; j) couty[i][j] ; } m1 (x[0][0] x[1][1]) * (y[0][0] y[1][1]); m2 (x[1][0] x[1][1]) * y[0][0]; m3 x[0][0] * (y[0][1] - y[1][1]); m4 x[1][1] * (y[1][0] - y[0][0]); m5 (x[0][0] x[0][1]) * y[1][1]; m6 (x[1][0] - x[0][0]) * (y[0][0]y[0][1]); m7 (x[0][1] - x[1][1]) * (y[1][0]y[1][1]); z[0][0] m1 m4- m5 m7; z[0][1] m3 m5; z[1][0] m2 m4; z[1][1] m1 - m2 m3 m6; cout\n使用 Strassen 算法得到的乘积 ; for(i 0; i 2 ; i) { coutendl; for(j 0; j 2; j) coutz[i][j] ; } return 0; }输出The first matrix is: 12 34 22 10 The second matrix is: 3 4 2 1 Product achieved using Strassens algorithm: 104 82 86 98public class Strassens { public static void main(String[] args) { int[][] x {{12, 34}, {22, 10}}; int[][] y {{3, 4}, {2, 1}}; int z[][] new int[2][2]; int m1, m2, m3, m4 , m5, m6, m7; System.out.print(第一个矩阵是 ); for(int i 0; i2; i) { System.out.println();//new line for(int j 0; j2; j) { System.out.print(x[i][j] \t); } } System.out.print(\n第二个矩阵是 ); for(int i 0; i2; i) { System.out.println();//new line for(int j 0; j2; j) { System.out.print(y[i][j] \t); } } m1 (x[0][0] x[1][1]) * (y[0][0] y[1][1]); m2 (x[1][0] x[1][1]) * y[0][0]; m3 x[0][0] * (y[0][1] - y[1][1]); m4 x[1][1] * (y[1][0] - y[0][0]); m5 (x[0][0] x[0][1]) * y[1][1]; m6 (x[1][0] - x[0][0]) * (y[0][0]y[0][1]); m7 (x[0][1] - x[1][1]) * (y[1][0]y[1][1]); z[0][0] m1 m4- m5 m7; z[0][1] m3 m5; z[1][0] m2 m4; z[1][1] m1 - m2 m3 m6; System.out.print(\n使用 Strassen 算法得到的乘积 ); for(int i 0; i2; i) { System.out.println();//new line for(int j 0; j2; j) { System.out.print(z[i][j] \t); } } } }输出The first matrix is: 12 34 22 10 The second matrix is: 3 4 2 1 Product achieved using Strassens algorithm: 104 82 86 98import numpy as np x np.array([[12, 34], [22, 10]]) y np.array([[3, 4], [2, 1]]) z np.zeros((2, 2)) m1, m2, m3, m4, m5, m6, m7 0, 0, 0, 0, 0, 0, 0 print(第一个矩阵是 ) for i in range(2): print() for j in range(2): print(x[i][j], end\t) print(\n第二个矩阵是 ) for i in range(2): print() for j in range(2): print(y[i][j], end\t) m1 (x[0][0] x[1][1]) * (y[0][0] y[1][1]) m2 (x[1][0] x[1][1]) * y[0][0] m3 x[0][0] * (y[0][1] - y[1][1]) m4 x[1][1] * (y[1][0] - y[0][0]) m5 (x[0][0] x[0][1]) * y[1][1] m6 (x[1][0] - x[0][0]) * (y[0][0] y[0][1]) m7 (x[0][1] - x[1][1]) * (y[1][0] y[1][1]) z[0][0] m1 m4 - m5 m7 z[0][1] m3 m5 z[1][0] m2 m4 z[1][1] m1 - m2 m3 m6 print(\n使用 Strassen 算法得到的乘积 ) for i in range(2): print() for j in range(2): print(z[i][j], end\t)输出The first matrix is: 12 34 22 10 The second matrix is: 3 4 2 1 Product achieved using Strassens algorithm: 104.0 82.0 86.0 98.0