2.1. 标准方法
我们通常怎么做矩阵乘法？
给定 \(n \times n\) 矩阵 \(A\) 和 \(B\)，
标准方法是按如下方式计算 \(C = A \times B\) 中的元素
\(c_{ij}\)：
\[c_{ij} = \sum_{k=1}^n a_{ik}b_{kj}.\]
这需要 \(\Theta(n^3)\) 次乘法和
\(\Theta(n^3)\) 次加法。
不过，它并不像乍看起来那么糟，因为输入规模
不是 \(n\)，而是 \(n^2\)。
但这真的是我们能做得最好的吗？
考虑一下：任何矩阵乘法算法的朴素下界
都是 \(\Omega(n^2)\)，因为我们要创建
\(n^2\) 个输出。
暂时先考虑两个 \(2 \times 2\) 矩阵相乘。
基本算法需要恰好 8 次乘法和 4
次加法。
但考虑下面这个替代方案。
计算：
\[\begin{split}\begin{eqnarray*}
m_1 &=& (a_{12} - a_{22})(b_{21} + b_{22})\\
m_2 &=& (a_{11} + a_{22})(b_{11} + b_{22})\\
m_3 &=& (a_{11} - a_{21})(b_{11} + b_{12})\\
m_4 &=& (a_{11} + a_{12})b_{22}\\
m_5 &=& a_{11}(b_{12} - b_{22})\\
m_6 &=& a_{22}(b_{21} - b_{11})\\
m_7 &=& (a_{21} + a_{22})b_{11}
\end{eqnarray*}\end{split}\]
然后：
\[\begin{split}\begin{eqnarray*}
c_{11} &=& m_1 + m_2 - m_4 + m_6\\
c_{12} &=& m_4 + m_5\\
c_{21} &=& m_6 + m_7\\
c_{22} &=& m_2 - m_3 + m_5 - m_7
\end{eqnarray*}\end{split}\]
要验证这个看起来是正确的，让我们检查其中一个：
\[\begin{split}\begin{eqnarray*}
c_{11} &=& m_1 + m_2 - m_4 + m_6\\
&=& (a_{12} - a_{22})(b_{21} + b_{22}) + (a_{11} + a_{22})(b_{11} + b_{22})\\
&&\qquad- (a_{11} + a_{12})b_{22} + a_{22}(b_{21} - b_{11})\\
&=& a_{12}b_{21} + a_{12}b_{22} - a_{22}b_{21} - a_{22}b_{22} +
a_{11}b_{22} + a_{22}b_{11}\\
&&\qquad + a_{22}b_{22} - a_{11}b_{22} -
a_{12}b_{22} + a_{22}b_{21} - a_{22}b_{11}\\
&=& a_{11}b_{11} + a_{12}b_{21}
\end{eqnarray*}\end{split}\]
这需要 7 次乘法和 18 次加法／减法。
现在，如果我们实际在乘法 \(2 \times 2\) 数组，那
看起来不像是一种胜利，因为在乘
整数（甚至浮点数）时，乘法与加法的代价差别
并不大。
但请考虑，这在乘两个规模为 \(2n \times 2n\) 的矩阵时
同样适用。
在这种情况下，乘法是对半规模（\(n \times
n\)）矩阵进行的。
而在此情形下，矩阵乘法远比矩阵加法昂贵
（\(\Theta(n^3)\) 对 \(\Theta(n^2)\)）。
2.2. 斯特拉森算法
上面展示的、乘法次数减少的这种安排在数学上
众所周知，就是斯特拉森算法。
斯特拉森算法在 \(2n \times 2n\) 的情形下，用更多的加法／减法
换取更少的乘法。
它使用分治，试图减少乘大矩阵的总工作量。
正如我们已经看到的，在直接实现中，$2 times 2$ 的情况将完成这项工作：
\[\begin{split}\begin{eqnarray*}
c_{11} = a_{11}b_{11} + a_{12}b_{21}\\
c_{12} = a_{11}b_{12} + a_{12}b_{22}\\
c_{21} = a_{21}b_{11} + a_{22}b_{21}\\
c_{22} = a_{21}b_{12} + a_{22}b_{22}
\end{eqnarray*}\end{split}\]
把两个 \(2n \times 2n\) 矩阵相乘需要 8 次（矩阵）乘法
和 4 次（矩阵）加法。
考虑这个分治步骤：
假设 \(n\) 是 2 的幂。
用 \(\frac{n}{2} \times \frac{n}{2}\) 的矩阵来表示
\(C = A \times B\)。
\[\begin{split}\left[
\begin{array}{ll}
C_{11} & C_{12}\\
C_{21} & C_{22}
\end{array}
\right]
==========
\left[
\begin{array}{ll}
A_{11} & A_{12}\\
A_{21} & A_{22}
\end{array}
\right]
\left[
\begin{array}{ll}
B_{11} & B_{12}\\
B_{21} & B_{22}
\end{array}
\right]\end{split}\]
按照斯特拉森算法，这可以用 7 次乘法
和 18 次加法／减法计算 \(n/2 \times n/2\) 矩阵来实现。
这给出下面的递推关系，以及
应用主定理得到的这个解：
\[\begin{split}\begin{eqnarray*}
T(n) &=& 7T(n/2) + 18(n/2)^2\\
T(n) &=& \Theta(n^{\log_2 7}) = \Theta(n^{2.81}).
\end{eqnarray*}\end{split}\]
这显然比 \(\Theta(n^3)\) 增长得慢。
然而，由于加法次数的增加，存在大得多的常数。
斯特拉森算法只有在矩阵非常巨大时
才切实可行。
还有一些其他安排可以进一步压低指数。
当前"最快"的算法（在渐近意义上）是
\(\Theta(n^{2.376})\)。
但由于大量加法带来的额外开销，
它甚至比斯特拉森算法更不实用。
矩阵乘法能否以 \(O(n^2)\) 时间完成，
在理论上仍是一个悬而未决的问题。
