algorithm - 带递归的 Strassen 子三次矩阵乘法算法

Question

我很难构思如何实现 Strassen 版本的该算法。

对于背景，我有以下迭代版本的伪代码:

def Matrix(a,b):
    result = []

    for i in range(0,len(a)):
        new_array = []
        result.extend(new_array)
        for j in range(0,len(b[0])):
            ssum = 0
            for k in range(0,len(a[0])):
                ssum += a[i][k] * b[k][j]
            result[i][j] = ssum
    return result

我还有以下初始分而治之版本的伪代码:

def recMatrix(x,y):
    if(len(x) == 1):
        return x[0] * y[0]

    z = []
    z[0] = recMatrix(x[0], y[0]) + recMatrix(x[1], y[2])
    z[1] = recMatrix(x[0], y[1]) + recMatrix(x[1], y[3])
    z[2] = recMatrix(x[2], y[0]) + recMatrix(x[3], y[2])
    z[3] = recMatrix(x[2], y[1]) + recMatrix(x[3], y[3])

    return z

所以我的问题是，我对分而治之法的理解是否正确？如果正确，我该如何修改以允许施特拉森法？ (这不是作业。)

(特别是我很难概念化它的地方是在递归之前(或之后)实体本身的数学。即 P1 = A(F-H)。如果递归主动乘以基本元素，如何strassen 递归处理矩阵的算术运算(加减)吗？我有以下伪代码来显示我的大脑在哪里:

def recMatrix(x,y):
    if(len(x) == 1):
        return x[0] * y[0]

    z = []
    p1 = recMatrix2(x[0], (y[1] - y[3]));
    p2 = recMatrix2(y[3], (x[0] + x[1]));
    p3 = recMatrix2(y[0], (x[2] + x[3]));
    p4 = recMatrix2(x[3], (y[2] - y[0]));
    p5 = recMatrix2((x[0] + x[3]), (y[0] + y[3]));
    p6 = recMatrix2((x[1] - x[3]), (y[2] + y[3]));
    p7 = recMatrix2((x[0] - x[3]), (y[0] + y[3]));

    z[0] = p5 + p4 - p2 + p6;
    z[1] = p1 + p2;
    z[2] = p3 + p4;
    z[3] = p1 + p5 - p3 - p7;

    return z

Answer 1

最后一段代码的问题是它没有采用正确的子矩阵。例如，在 p1 中，您想要获取 x 的左上角子矩阵，但您使用的是 x[0]，它只是x。您需要一些代码将矩阵分成 4 个较小的矩阵。或者你可以使用像 numpy 这样的数学库:

In [14]: from numpy import *

In [15]: x=range(16)

In [16]: x=reshape(x,(4,4))

In [17]: x
Out[17]: 
array([[ 0,  1,  2,  3],
       [ 4,  5,  6,  7],
       [ 8,  9, 10, 11],
       [12, 13, 14, 15]])

In [18]: x[0:2,0:2]
Out[18]: 
array([[0, 1],
      [4, 5]])

In [19]: x[2:4,2:4]
Out[19]: 
array([[10, 11],
       [14, 15]])