传统算法

  Strassen算法将2X2矩阵的乘法次数从8次减少到了7次。在介绍strassen算法之前，先用传统的算法计算一下2*2的矩阵乘法。
$$\begin{gathered} A=\left[\begin{array}{cc}1& 2\\ 3& 4\end{array}\right] \\ B=\left[\begin{array}{cc}5& 6\\ 7& 8\end{array}\right] \\ A\times B=\left[\begin{array}{cc}1\times 5+2\times 7& 1\times 6+2\times 8\\ 3\times 5+4\times 7& 3\times 6+4\times 8\end{array}\right]=\left[\begin{array}{cc}19& 22\\ 43& 50\end{array}\right] \end{gathered}$$
  总共使用了8次乘法和4次加法。

Strassen算法

  Strassen算法使用了7个中间变量，巧妙地用7次乘法合18次加法，减少了1次乘法操作，提高了算法的性能。其算法如下：
  设矩阵A、B为：
$$\begin{gathered} A=\left[\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right] \\ B=\left[\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right] \end{gathered}$$
  建立7个临时变量$P_1$到$P_7$，每个变量使用一次乘法运算。
$$\begin{gathered} P_1=(A_{11}+A_{22})(B_{11}+B_{22}) \\ {P}_2=(A_{21}+A_{22})B_{11} \\ {P}_3=A_{11}(B_{12}-B_{22}) \\ {P}_4=A_{22}(B_{21}-B_{11}) \\ {P}_5=(A_{11}+A_{12})B_{22} \\ {P}_6=(A_{21}-A_{11})(B_{11}+B_{12}) \\ {P}_7=(A_{12}-A_{22})(B_{21}+B_{22}) \\ {C}_{11}=P_1+P_4-P_5+P_7 \\ {C}_{12}=P_3+P_5 \\ {C}_{21}=P_2+P_4 \\ {C}_{22}=P_1-P_2+P_3+P_6 \\ A\times B=\left[\begin{array}{cc}{C}_{11}& C_{12}\\ C_{21}& C_{22}\end{array}\right] \end{gathered}$$
  公式比较复杂，总共11个公式呢，根本记不住，所以我建议，收藏我的博文，不要去记忆，当然也可以顺便关注我一波。
  需要注意的是上面11个公式中，乘法的左右顺序特别重要，因为这个公式可以适用于任何代数环。代数环就是乘法不需要符合交换律的集合、加法与乘法运算符。这意味着什么，这意味着2X2矩阵中的元素不仅可以是数字，还可以是矩阵。也就是说可以利用分块矩阵的方法，将大矩阵拆分为2X2的矩阵再使用Strassen算法。
  不过需要注意的是因为存在$A_{11}+A_{22}$这样的骚操作，所以进行矩阵分块时，行数或者列数不能是奇数，所以在为奇数的时候还是要用传统的方法啊。

python实现

  跟我以往的文章不同，这次我没有把本文的算法代码和其他博文的代码混在一起。我新写了一个python文件，只做Strassen算法，而且使用了分治以处理大矩阵，代码如下：

class Matrix:
    # 矩阵
    @staticmethod
    def create_by_lines(lines):
        # 为了支持分块，设置四个属性
        return Matrix(lines, 0, len(lines), 0, len(lines[0]))

    def __init__(self, lines, row_start, row_end, column_start, column_end):
        self.__lines = lines
        # 为了支持分块，设置四个属性
        self.__column_start = column_start
        self.__column_end = column_end
        self.__row_start = row_start
        self.__row_end = row_end

    def __mul__(self, other):
        # 首先判断能不能相乘
        if self.column_len() != other.row_len():
            raise Exception("矩阵A列数%d != 矩阵B的行数%d" % (len(self.__lines[0]), len(other.__lines)))
        # 然后判断是不是2X2矩阵
        # 这里场景比较多：
        # 1 1 x n n x 1
        # 2 n x 1 1 x n
        # 3 2 x 2 2 x 2 strassen 数值运算
        # 4 其他，进行分块 strassen 矩阵运算
        if self.row_len() == 1 or self.column_len() == 1:
            return self.plain_mul(other)

        # 奇数不能分块
        if self.row_len() & 1 == 1 or self.column_len() & 1 == 1 or other.row_len() & 1 == 1:
            return self.plain_mul(other)

        # 这个时候就可以使用strassen算法了

        a11, a12, a21, a22 = self.sub()
        b11, b12, b21, b22 = other.sub()

        p1 = (a11 + a22) * (b11 + b22)
        p2 = (a21 + a22) * b11
        p3 = a11 * (b12 - b22)
        p4 = a22 * (b21 - b11)
        p5 = (a11 + a12) * b22
        p6 = (a21 - a11) * (b11 + b12)
        p7 = (a12 - a22) * (b21 + b22)

        return Matrix.create(p1 + p4 - p5 + p7, p3 + p5, p2 + p4, p1 - p2 + p3 + p6)

    def __add__(self, other):
        arr = [[0] * self.column_len() for _ in range(0, self.row_len())]
        # 里面不能是同一个数组
        for i in range(0, self.row_len()):
            self_row = self.__lines[self.__row_start + i]
            other_row = other.__lines[other.__row_start + i]
            for j in range(0, self.column_len()):
                arr[i][j] = self_row[self.__column_start + j] + other_row[other.__column_start + j]
        return Matrix.create_by_lines(arr)

    def __sub__(self, other):
        arr = [[0] * self.column_len() for _ in range(0, self.row_len())]
        # 里面不能是同一个数组
        for i in range(0, self.row_len()):
            self_row = self.__lines[self.__row_start + i]
            other_row = other.__lines[other.__row_start + i]
            for j in range(0, self.column_len()):
                arr[i][j] = self_row[self.__column_start + j] - other_row[other.__column_start + j]
        return Matrix.create_by_lines(arr)

    def plain_mul(self, other):
        # 弄一个m行n列的新矩阵
        m = self.row_len()
        n = other.column_len()
        p = other.row_len()

        result = [[0] * n for _ in range(0, m)]
        # i 代表 A矩阵的行
        for i in range(self.__row_start, self.__row_end):
            # j 代表 B 矩阵的列
            for j in range(other.__column_start, other.__column_end):
                # 第一个矩阵的行 与第二个矩阵列的乘积和
                # k 代表 A矩阵的列和B矩阵的行
                for k in range(0, p):
                    self_line = self.__lines[i]
                    other_line = other.__lines[other.__row_start + k]
                    a = self_line[self.__column_start + k]
                    b = other_line[j]
                    mul = a * b
                    result[i - self.__row_start][j - other.__column_start] += mul
        return Matrix.create_by_lines(result)

    def row_len(self):
        return self.__row_end - self.__row_start

    def column_len(self):
        return self.__column_end - self.__column_start

    def sub(self):
        a_middle_row = (self.__row_end + self.__row_start) // 2
        a_middle_column = (self.__column_end + self.__column_start) // 2
        a11 = Matrix(self.__lines, self.__row_start, a_middle_row, self.__column_start, a_middle_column)
        a12 = Matrix(self.__lines, self.__row_start, a_middle_row, a_middle_column, self.__column_end)
        a21 = Matrix(self.__lines, a_middle_row, self.__row_end, self.__column_start, a_middle_column)
        a22 = Matrix(self.__lines, a_middle_row, self.__row_end, a_middle_column, self.__column_end)
        return a11, a12, a21, a22

    @staticmethod
    def create(a11, a12, a21, a22):
        len_rows = a11.row_len() + a21.row_len()
        len_columns = a11.column_len() + a12.column_len()
        lines = [[0] * len_columns for _ in range(0, len_rows)]
        # 拷贝进去
        a11.copy_to(lines, 0, 0)
        a12.copy_to(lines, 0, a11.column_len())
        a21.copy_to(lines, a11.row_len(), 0)
        a22.copy_to(lines, a12.row_len(), a21.column_len())
        return Matrix.create_by_lines(lines)

    def copy_to(self, lines, row_start, column_start):
        for i in range(0, self.row_len()):
            self_row = self.__lines[self.__row_start + i]
            other_row = lines[row_start + i]
            for j in range(0, self.column_len()):
                other_row[column_start + j] = self_row[self.__column_start + j]

    @property
    def lines(self):
        return self.__lines