递归方法求矩阵相乘c++

矩阵相乘的递归方法也称为 Strassen 矩阵相乘算法，其时间复杂度为 $O(n^{log_2{7}})$，比普通矩阵相乘的时间复杂度 $O(n^3)$ 更优秀。

假设有两个 $n\times n$ 的矩阵 $A$ 和 $B$，它们的乘积 $C=AB$ 可以递归地分解为：

$$
C = \begin{bmatrix}C_{11} & C_{12}\\ C_{21} & C_{22}\end{bmatrix} = \begin{bmatrix}A_{11} & A_{12}\\ A_{21} & A_{22}\end{bmatrix}\begin{bmatrix}B_{11} & B_{12}\\ B_{21} & B_{22}\end{bmatrix}
$$

其中 $C_{11},C_{12},C_{21},C_{22}$ 均为 $\frac{n}{2}\times\frac{n}{2}$ 的矩阵，它们的计算公式为：

$$
\begin{aligned}
C_{11} &= M_1 + M_4 - M_5 + M_7\\
C_{12} &= M_3 + M_5\\
C_{21} &= M_2 + M_4\\
C_{22} &= M_1 - M_2 + M_3 + M_6\\
\end{aligned}
$$

其中 $M_1\sim M_7$ 均为 $\frac{n}{2}\times\frac{n}{2}$ 的矩阵，它们的计算公式为：

$$
\begin{aligned}
M_1 &= (A_{11}+A_{22})(B_{11}+B_{22})\\
M_2 &= (A_{21}+A_{22})B_{11}\\
M_3 &= A_{11}(B_{12}-B_{22})\\
M_4 &= A_{22}(B_{21}-B_{11})\\
M_5 &= (A_{11}+A_{12})B_{22}\\
M_6 &= (A_{21}-A_{11})(B_{11}+B_{12})\\
M_7 &= (A_{12}-A_{22})(B_{21}+B_{22})\\
\end{aligned}
$$

下面是递归方法求矩阵相乘的 Python 代码实现：

def matrix_multiply_recursive(A, B):
    n = len(A)
    # base case
    if n == 1:
        return [[A[0][0] * B[0][0]]]
    # divide
    A11 = [A[i][:n//2] for i in range(n//2)]
    A12 = [A[i][n//2:] for i in range(n//2)]
    A21 = [A[i][:n//2] for i in range(n//2, n)]
    A22 = [A[i][n//2:] for i in range(n//2, n)]
    B11 = [B[i][:n//2] for i in range(n//2)]
    B12 = [B[i][n//2:] for i in range(n//2)]
    B21 = [B[i][:n//2] for i in range(n//2, n)]
    B22 = [B[i][n//2:] for i in range(n//2, n)]
    # conquer
    M1 = matrix_multiply_recursive(matrix_add(A11, A22), matrix_add(B11, B22))
    M2 = matrix_multiply_recursive(matrix_add(A21, A22), B11)
    M3 = matrix_multiply_recursive(A11, matrix_sub(B12, B22))
    M4 = matrix_multiply_recursive(A22, matrix_sub(B21, B11))
    M5 = matrix_multiply_recursive(matrix_add(A11, A12), B22)
    M6 = matrix_multiply_recursive(matrix_sub(A21, A11), matrix_add(B11, B12))
    M7 = matrix_multiply_recursive(matrix_sub(A12, A22), matrix_add(B21, B22))
    C11 = matrix_add(matrix_sub(matrix_add(M1, M4), M5), M7)
    C12 = matrix_add(M3, M5)
    C21 = matrix_add(M2, M4)
    C22 = matrix_add(matrix_add(matrix_sub(M1, M2), M3), M6)
    # combine
    C = [[0] * n for _ in range(n)]
    for i in range(n//2):
        C[i][:n//2] = C11[i]
        C[i][n//2:] = C12[i]
    for i in range(n//2, n):
        C[i][:n//2] = C21[i-n//2]
        C[i][n//2:] = C22[i-n//2]
    return C

def matrix_add(A, B):
    return [[A[i][j] + B[i][j] for j in range(len(A[0]))] for i in range(len(A))]

def matrix_sub(A, B):
    return [[A[i][j] - B[i][j] for j in range(len(A[0]))] for i in range(len(A))]

# 测试
A = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
B = [[17, 18, 19, 20], [21, 22, 23, 24], [25, 26, 27, 28], [29, 30, 31, 32]]
C = matrix_multiply_recursive(A, B)
for row in C:
    print(row)

输出结果为：

[250, 260, 270, 280]
[618, 644, 670, 696]
[986, 1028, 1070, 1112]
[1354, 1412, 1470, 1528]