矩阵乘法

问题描述

两个 $n \times n$ 的矩阵 $A$ 和 $B$ 相乘，通常算法时间复杂度为 $O (n^{3})$ 。是否存在分治算法可以降低时间复杂度？

将 $A$ 和 $B$ 分成 4 个大小为 $\frac{n}{2} \times \frac{n}{2}$ 的子矩阵相乘。

\begin{array}{l} [\begin{array}{ll} C_{11} & C_{12} \\ C_{21} & C_{22} \end{array}] = [\begin{array}{ll} A_{11} & A_{12} \\ A_{21} & A_{22} \end{array}] [\begin{array}{ll} B_{11} & B_{12} \\ B_{21} & B_{22} \end{array}] \end{array}

需要计算的子问题包括 8 个小矩阵乘法以及 4 个矩阵加法，时间复杂度为：

\begin{array}{r} T (n) = 8 T (\frac{n}{2}) + Θ (n^{2}) \end{array}

即使如此，计算得到的时间复杂度没有得到改善，仍为 $T (n^{3})$ 。我们可令

\begin{aligned} M_{1} & = A_{11} (B_{12} - B_{22}) \\ M_{2} & = (A_{11} + A_{12}) B_{22} \\ M_{3} & = (A_{21} + A_{22}) B_{11} \\ M_{4} & = A_{22} (B_{21} - B_{11}) \\ M_{5} & = (A_{11} + A_{22}) (B_{11} + B_{22}) \\ M_{6} & = (A_{12} - A_{22}) (B_{21} + B_{22}) \\ M_{7} & = (A_{11} - A_{21}) (B_{11} + B_{12}) \end{aligned}

于是

\begin{array}{r} C_{11} = M_{5} + M_{4} - M_{2} + M_{6} \\ C_{12} = M_{1} + M_{2} \\ C_{21} = M_{3} + M_{4} \\ C_{22} = M_{5} + M_{1} - M_{3} - M_{7} \end{array}

这样就把 8 个矩阵相乘转变成 7 个矩阵相乘，时间复杂度降低为

\begin{aligned} T (n) & = 7 T (\frac{n}{2}) + Θ (n^{2}) \\ = Θ (n^{\log_{2} 7}) \end{aligned}