矩阵乘法

假设A和B为n阶矩阵（ $n = 2^k$ ），计算时，对于C中 $n^2$ 个元素，每个元素都需要做n次乘法，因此 $W(n) = O(n^3)$ 。

利用简单的分治策略，可以将矩阵分块计算。

\begin{aligned} \left( \begin{matrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} \right) \left( \begin{matrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{matrix} \right) = \left( \begin{matrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{matrix} \right) \end{aligned}

其中，

\begin{aligned} 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{aligned}

这样就把原问题转换为了8个子问题，递推方程为：

\begin{aligned} W(n) = \begin{cases} 1 & n = 1 \\ 8W(n/2) + cn^2 & n > 1 \end{cases} \end{aligned}

求解得到：

W(n) = O(n^3)

简单的分治算法并不能降低时间复杂度的阶，但是矩阵乘法可以通过减少子问题的个数进行优化。

题目

分块矩阵乘积的C₁₂应该是哪一个？

Strassen矩阵乘法

让 $M_1,\ M_2,\ \dots,\ M_7$ 分别对应矩阵乘法的7个子问题：

\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{aligned} 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{aligned}

在这些运算中，一共有7个子问题和18次矩阵加减法，时间复杂度为：

\begin{aligned} W(n) = \begin{cases} 1 & n = 1 \\ 7W(n/2) + 18(n/2)^2 & n > 1 \end{cases} \end{aligned}

求解得到：

W(n) = O(n^{\log_2 7}) \approx O(n^{2.8075})

Coppersmith-Winograd算法曾将矩阵乘法的时间复杂度上界改进到 $O(n^{2.376})$ ，后续研究进一步改进了这一上界。矩阵乘法可以应用在科学计算、图形处理、数据挖掘等方面，在回归、聚类、主成分分析、决策树等挖掘算法中常常涉及大规模矩阵运算。

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

题目

Strassen为什么能降低渐近复杂度？

题目

能否把M₁=A₁₁(B₁₂−B₂₂)写成(B₁₂−B₂₂)A₁₁？

给定A=[[2,1],[3,4]]，B=[[5,2],[1,3]]。用正文的Strassen公式计算AB，在纸上写出过程，不交换矩阵乘法的顺序。

逐项计算M₁至M₇。
用中间结果组合C₁₁、C₁₂、C₂₁、C₂₂。
用普通矩阵乘法核对答案，并比较乘法次数。

矩阵乘法

假设A和B为n阶矩阵（ $n = 2^k$ ），计算时，对于C中 $n^2$ 个元素，每个元素都需要做n次乘法，因此 $W(n) = O(n^3)$ 。

利用简单的分治策略，可以将矩阵分块计算。

\begin{aligned} \left( \begin{matrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} \right) \left( \begin{matrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{matrix} \right) = \left( \begin{matrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{matrix} \right) \end{aligned}

其中，

\begin{aligned} 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{aligned}

这样就把原问题转换为了8个子问题，递推方程为：

\begin{aligned} W(n) = \begin{cases} 1 & n = 1 \\ 8W(n/2) + cn^2 & n > 1 \end{cases} \end{aligned}

求解得到：

W(n) = O(n^3)

简单的分治算法并不能降低时间复杂度的阶，但是矩阵乘法可以通过减少子问题的个数进行优化。

题目

分块矩阵乘积的C₁₂应该是哪一个？

Strassen矩阵乘法

让 $M_1,\ M_2,\ \dots,\ M_7$ 分别对应矩阵乘法的7个子问题：

\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{aligned} 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{aligned}

在这些运算中，一共有7个子问题和18次矩阵加减法，时间复杂度为：

\begin{aligned} W(n) = \begin{cases} 1 & n = 1 \\ 7W(n/2) + 18(n/2)^2 & n > 1 \end{cases} \end{aligned}

求解得到：

W(n) = O(n^{\log_2 7}) \approx O(n^{2.8075})

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

题目

Strassen为什么能降低渐近复杂度？

题目

能否把M₁=A₁₁(B₁₂−B₂₂)写成(B₁₂−B₂₂)A₁₁？

给定A=[[2,1],[3,4]]，B=[[5,2],[1,3]]。用正文的Strassen公式计算AB，在纸上写出过程，不交换矩阵乘法的顺序。

逐项计算M₁至M₇。
用中间结果组合C₁₁、C₁₂、C₂₁、C₂₂。
用普通矩阵乘法核对答案，并比较乘法次数。

矩阵乘法

矩阵乘法

矩阵乘法

知识测验

Strassen矩阵乘法

Strassen：计算七个乘积，再组合矩阵

知识测验

知识测验

手算七个中间乘积

矩阵乘法

矩阵乘法

矩阵乘法

知识测验

Strassen矩阵乘法

Strassen：计算七个乘积，再组合矩阵

知识测验

知识测验

手算七个中间乘积