CSCI3160 L02 · Part 4/4 Strassen矩阵乘法

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L02，第 4 部分 / 共 4 部分 · 原件 L02-Divide-and-Conquer-未核.pdf（本地课件） p.23–28 定位：逐个验证七个乘积如何恢复四个输出块，并推导矩阵乘法复杂度。前后：上一份 Part 3

Matrix Multiplication

p.23 分节页。

矩阵表示与七次乘法（p.24–25）【新】

p.24 We store an $n\times n$ matrix with an array of length $n^2$ in “row-major” order.

公式按讲义重排。p.24 的行优先（row-major）存储先放第一行再放第二行。讲义矩阵第一行为 1、2，第二行为 3、4，对应数组 [1,2,3,4]。采用从 1 开始的索引时，元素 $(i,j)$ 的位置是 $(i-1)n+j$ ；例如 $(2,1)$ 在第 3 格。普通乘法每个结果算 $n$ 项内积，共 $n^2$ 个结果，所以 $O(n^3)$ 。

题面（同原件 · Warm Up · p.25）

p.25 How many multiplication operations do we need to perform?

题面中待计算的矩阵乘积如下，保留原排布（公式按讲义重排）：

\begin{pmatrix}a&b\\c&d\end{pmatrix} \begin{pmatrix}e&f\\g&h\end{pmatrix}.

p.25 的通常方法有四个输出，每个做两次乘法，共八次。Strassen 换成七个中间积：

\begin{aligned} p_1&=a(f-h),&p_2&=(a+b)h,\\ p_3&=(c+d)e,&p_4&=d(g-e),\\ p_5&=(a+d)(e+h),&p_6&=(b-d)(g+h),\\ p_7&=(a-c)(e+f). \end{aligned}

结果四格分别是 $p_5+p_4-p_2+p_6$ 、 $p_1+p_2$ 、 $p_3+p_4$ 、 $p_1+p_5-p_3-p_7$ 。它用额外加减法换掉一次乘法。

补充／算一遍（数字是我为演示取的，讲义没给）：让 $a,b,c,d=1,2,3,4$ ， $e,f,g,h=5,6,7,8$ ，七个积依次为 $-2,24,35,8,65,-30,-22$ 。左上格 $65+8-24-30=19$ ，右上格 $-2+24=22$ ，左下格 $35+8=43$ ，右下格 $-2+65-35+22=50$ 。普通乘法左上格为 $1\cdot5+2\cdot7=19$ ，其余三格也分别为 22、43、50。为了知道七个积对任意输入都成立，在此逐格核对：

逐格展开并消去配对项，保留因子原顺序：

\begin{aligned} p_5+p_4-p_2+p_6 &=(ae+ah+de+dh)+(dg-de)-(ah+bh)\\ &\quad +(bg+bh-dg-dh)\\ &=ae+bg,\\ p_1+p_2&=(af-ah)+(ah+bh)=af+bh,\\ p_3+p_4&=(ce+de)+(dg-de)=ce+dg,\\ p_1+p_5-p_3-p_7 &=(af-ah)+(ae+ah+de+dh)-(ce+de)\\ &\quad -(ae+af-ce-cf)\\ &=cf+dh. \end{aligned}

四项恰好是普通矩阵乘法的四个输出。因所有展开均保持左矩阵因子在左，证明也能用于 p.27 的矩阵块。

原核验位置仍保留见附录 A3。

从数字推广到矩阵块（p.26–28）

p.26 Divide each of A and B into 4 submatrices of order n/2:

p.26 的每个“大格”改为 $n/2$ 阶矩阵。加减同形状矩阵需逐格操作，代价 $O(n^2)$ ；乘两个块则是递归子问题。p.27 将刚才的 $a,b,c,d$ 换成 $A_{11},A_{12},A_{21},A_{22}$ ，把 $e,f,g,h$ 换成 B 的相应四块，仍只做七次递归乘法。分配律保持成立，且没有颠倒 A 与 B 的乘法次序，这一点对矩阵至关重要。

p.26 的普通分块乘法四项分别是 $A_{11}B_{11}+A_{12}B_{21}$ 、 $A_{11}B_{12}+A_{12}B_{22}$ 、 $A_{21}B_{11}+A_{22}B_{21}$ 、 $A_{21}B_{12}+A_{22}B_{22}$ 。每项两个块乘积，共八次。p.27 的七个递归输入不能仅凭“类似标量”省去：

\begin{aligned} P_1&=A_{11}(B_{12}-B_{22}),\\ P_2&=(A_{11}+A_{12})B_{22},\\ P_3&=(A_{21}+A_{22})B_{11},\\ P_4&=A_{22}(B_{21}-B_{11}),\\ P_5&=(A_{11}+A_{22})(B_{11}+B_{22}),\\ P_6&=(A_{12}-A_{22})(B_{21}+B_{22}),\\ P_7&=(A_{11}-A_{21})(B_{11}+B_{12}). \end{aligned}

输出按左上、右上、左下、右下依次拼成 $P_5+P_4-P_2+P_6$ 、 $P_1+P_2$ 、 $P_3+P_4$ 、 $P_1+P_5-P_3-P_7$ 。每个 P 都是半阶矩阵，不是一个数；计算它的准备加减为 $O(n^2)$ ，乘法为 $f(n/2)$ 。七是固定常数，合起来仍为七次递归加 $O(n^2)$ 。

p.28 $f(n)\le7f(n/2)+O(n^2)$

公式按讲义重排。p.28 的叶子数为 $7^{\log_2 n}=n^{\log_2 7}$ ；每层加减工作按因子 $7/4$ 增大，所以底层主导，总时间 $O(n^{\log_2 7})$ ，其中 $\log_2 7\approx2.807$ ，讲义写为 $O(n^{2.81})$ 。算一遍： $n=4$ 时，普通递归有 $8^2=64$ 个标量乘法，Strassen 有 $7^2=49$ 个，但同时多了加减法；渐近更快不表示任意小矩阵实际用时更短。

补充：为什么七次递归带来的是指数变化。 对规模 $n=2^h$ ，第 j 层有 $7^j$ 个子调用，每个块边长 $n/2^j$ 。一次块加减必须访问其全部元素，故该层总加减量与 $n^2(7/4)^j$ 同阶。公比大于 1，最深层附近最贵；把这一层级数加完，与最后一层同阶，而最后一层为 $n^2(7/4)^h=n^{\log_2 7}$ 。省一次乘法的效应在每一层重复，不只是最终运行时间乘上 $7/8$ 。

自测：为何不能把块矩阵公式中的 de 随手换成 ed？

数的乘法可交换，但矩阵乘法一般不可交换。取自演示矩阵

D=\begin{pmatrix}1&0\\0&0\end{pmatrix},\qquad E=\begin{pmatrix}0&1\\0&0\end{pmatrix}.

有 $DE=E$ 、 $ED=0$ 。因此附录里的抵消必须依赖相同顺序的项相消，不能靠交换因子来制造抵消。这个条件解释了为何要逐格核对恒等式。

补充：回应 p.24 留下的任意阶数练习，补零到最近的 $N=2^{\lceil\log_2 n\rceil}<2n$ ，算出大矩阵积后取左上 $n\times n$ 块。补零不改变原元素的乘积，且 $N$ 只大常数倍，不改变渐近指数。

本讲核心考点

七个积取代八个积，并逐块验证恒等式（p.24–28；C 级）。
递推指数是log₂7，加减矩阵块仍需平方时间（p.28；C 级）。

附录

A3 七个积为何确实得到矩阵积（p.25）

逐格展开并消去配对项，保留因子原顺序：

\begin{aligned} p_5+p_4-p_2+p_6 &=(ae+ah+de+dh)+(dg-de)-(ah+bh)\\ &\quad +(bg+bh-dg-dh)\\ &=ae+bg,\\ p_1+p_2&=(af-ah)+(ah+bh)=af+bh,\\ p_3+p_4&=(ce+de)+(dg-de)=ce+dg,\\ p_1+p_5-p_3-p_7 &=(af-ah)+(ae+ah+de+dh)-(ce+de)\\ &\quad -(ae+af-ce-cf)\\ &=cf+dh. \end{aligned}

四项恰好是普通矩阵乘法的四个输出。因所有展开均保持左矩阵因子在左，证明也能用于 p.27 的矩阵块。

回到正文：矩阵表示与七次乘法（p.24–25）

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：L02-Divide-and-Conquer-未核.pdf（本地课件），本部分 p.23–28；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。