C#，数值计算，矩阵相乘的斯特拉森（Strassen’s Matrix Multiplication）分治算法与源代码

Volker Strassen

1 矩阵乘法

矩阵乘法是机器学习中最基本的运算之一，对其进行优化是多种优化的关键。通常，将两个大小为N X N的矩阵相乘需要N^3次运算。从那以后，我们在更好、更聪明的矩阵乘法算法方面取得了长足的进步。沃尔克·斯特拉森于1969年首次发表了他的算法。这是第一个证明基本O（n^3）运行时不是optiomal的算法。

Strassen算法的基本思想是将A和B分为8个子矩阵，然后递归计算C的子矩阵。这种策略称为分而治之。

2 伪代码

1. 如上图所示，将矩阵A和B划分为大小为N/2 x N/2的4个子矩阵。
2. 递归计算7个矩阵乘法。
3. 计算C的子矩阵。
4. 将这些子矩阵组合到我们的新矩阵C中

3 复杂性

1. 最坏情况时间复杂度：Θ（n^2.8074）
2. 最佳情况时间复杂度：Θ（1）
3. 空间复杂度：Θ（logn）

年青时正在发愁的  Volker Strassen

4 算法的详细解释

矩阵相乘在进行3D变换的时候是经常用到的。在应用中常用矩阵相乘的定义算法对其进行计算。这个算法用到了大量的循环和相乘运算，这使得算法效率不高。而矩阵相乘的计算效率很大程度上的影响了整个程序的运行速度，所以对矩阵相乘算法进行一些改进是必要的。

        我们先讨论二阶矩阵的计算方法。

        对于二阶矩阵

        a11    a12                    b11    b12    
        A =    a21    a22    B =    b21    b22
        先计算下面7个量(1)

        x1 = (a11 + a22) * (b11 + b22);
        x2 = (a21 + a22) * b11;
        x3 = a11 * (b12 - b22);
        x4 = a22 * (b21 - b11);
        x5 = (a11 + a12) * b22;
        x6 = (a21 - a11) * (b11 + b12);
        x7 = (a12 - a22) * (b21 + b22);
        再设C = AB。根据矩阵相乘的规则，C的各元素为(2)

        c11 = a11 * b11 + a12 * b21
        c12 = a11 * b12 + a12 * b22
        c21 = a21 * b11 + a22 * b21
        c22 = a21 * b12 + a22 * b22
        比较(1)(2)，C的各元素可以表示为(3)

        c11 = x1 + x4 - x5 + x7
        c12 = x3 + x5
        c21 = x2 + x4
        c22 = x1 + x3 - x2 + x6