strassen矩阵乘法分治法代码

这是一个非常流行的矩阵乘法实现算法，可以被实现为分治算法。以下是 Strassen 矩阵乘法的 Python 代码实现：

def strassen(A, B):
    n = len(A)
    if n == 1:
        return [[A[0][0] * B[0][0]]]

    # 创建一个空矩阵
    C = [[0 for i in range(n)] for j in range(n)]

    # 拆分输入矩阵
    A11, A12, A21, A22 = split(A)
    B11, B12, B21, B22 = split(B)

    # 递归计算 Strassen 矩阵乘法
    P1 = strassen(add(A11, A22), add(B11, B22))
    P2 = strassen(add(A21, A22), B11)
    P3 = strassen(A11, sub(B12, B22))
    P4 = strassen(A22, sub(B21, B11))
    P5 = strassen(add(A11, A12), B22)
    P6 = strassen(sub(A21, A11), add(B11, B12))
    P7 = strassen(sub(A12, A22), add(B21, B22))

    # 合并矩阵
    C11 = add(sub(add(P1, P4), P5), P7)
    C12 = add(P3, P5)
    C21 = add(P2, P4)
    C22 = add(sub(add(P1, P3), P2), P6)

    # 返回结果
    merge(C11, C12, C21, C22, C)
    return C

# 矩阵加法
def add(A, B):
    n = len(A)
    C = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            C[i][j] = A[i][j] + B[i][j]
    return C

# 矩阵减法
def sub(A, B):
    n = len(A)
    C = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            C[i][j] = A[i][j] - B[i][j]
    return C

# 拆分矩阵
def split(A):
    n = len(A) // 2
    A11 = [[0 for i in range(n)] for j in range(n)]
    A12 = [[0 for i in range(n)] for j in range(n)]
    A21 = [[0 for i in range(n)] for j in range(n)]
    A22 = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            A11[i][j] = A[i][j]
            A12[i][j] = A[i][j+n]
            A21[i][j] = A[i+n][j]
            A22[i][j] = A[i+n][j+n]
    return A11, A12, A21, A22

# 合并矩阵
def merge(A11, A12, A21, A22, A):
    n = len(A11)
    for i in range(n):
        for j in range(n):
            A[i][j] = A11[i][j]
            A[i][j+n] = A12[i][j]
            A[i+n][j] = A21[i][j]
            A[i+n][j+n] = A22[i][j]

这是一个 Python 实现的 Strassen 矩阵乘法分治法算法。