By Long Luo
机器学习中需要训练大量数据，涉及大量复杂运算，例如卷积、矩阵等。这些复杂运算不仅多，而且每次计算的数据量很大，如果能针对这些运算进行优化，可以大幅提高性能。
一、矩阵乘法
假设$A$为$m \times p$的矩阵，$B$为$p \times n$的矩阵，那么称$m \times n$的矩阵$C$为矩阵$A$与$B$的乘积，记作$C = AB$，称为矩阵积（matrix product）。
其中矩阵$C$中的第$i$行第$j$列元素可以表示为：
$$
(AB){ij} = \sum{k=1}^{p}{a_{ik}b_{kj}} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdot\cdot\cdot + a_{ip}b_{pj}
$$
如下图所示：
假如在矩阵$A$和矩阵$B$中，$m = p = n = N$，那么完成$C = AB$需要多少次乘法呢？
- 对于每一个行向量$r$ ，总共有$N$行；
- 对于每一个列向量$c$，总共有$N$列；
- 计算它们的内积，总共有$N$次乘法计算。
综合可以看出，矩阵乘法的算法复杂度是：$\Theta(N^{3})$。
二、Strassen算法
那么有没有比$\Theta(N^{3})$更快的算法呢？