专题进阶 · 并行算法推荐总顺序 · 第 110 / 148 课

先算清形状与行列内积,再用三个循环实现矩阵乘法并分析成本。

先学会这些,再进入本课 数组 时间复杂度
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 并行算法

矩阵乘法Matrix Multiplication

每个输出元素是行列内积,可按输出块并行,注意数据复用与带宽。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

先算清形状与行列内积,再用三个循环实现矩阵乘法并分析成本。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

A 有 2 行 3 列,B 有 3 行 2 列,为什么乘积是 2×2,每个输出元素究竟从哪里来?

02一步步得到方法

先检查形状,再计算数值

若 A 是 m×k,B 是 k×n,内侧维度 k 必须相等,乘积 C 的形状为 m×n。Cᵢⱼ=Σₚ₌₀ᵏ⁻¹ AᵢₚBₚⱼ:取 A 的第 i 行和 B 的第 j 列,逐项相乘后求和。

这不是对应位置逐元素相乘。逐元素乘法通常要求相同形状或约定广播,而矩阵乘法沿中间维度求和。把形状写在每一步旁边,可以提早发现大多数索引错误。

用线性变换理解顺序

矩阵可以表示线性变换。对列向量 x,ABx 表示先做 B,再做 A,因此一般 AB≠BA;有时反过来连形状都不合法。

矩阵乘法满足结合律,在尺寸允许时 (AB)C=A(BC),但中间形状和运算量可能不同。例如长链相乘时,改变括号次序可以极大降低成本,浮点结果也可能因求和次序略有差异。

三个循环各负责什么

最外层 i 选输出行,第二层 j 选输出列,最内层 p 扫过共有维度并累加。每个输出元素必须从 0 开始累计;若共用同一个 Python 内层列表创建所有行,会导致行之间意外联动。

下面是便于核对的 CPU 参考实现。实际高性能实现会重排循环、分块、向量化或调用 BLAS,但都必须保持同一形状和求和语义。

03把一个小例子完全算清楚

A=[[1,2,3],[4,5,6]],B=[[7,8],[9,10],[11,12]]。

步骤计算与状态为什么这样做
C₀₀1×7+2×9+3×11=58第 0 行与第 0 列
C₀₁1×8+2×10+3×12=64第 0 行与第 1 列
第 1 行[139,154]使用 A 的下一行

窄屏可左右滑动表格,阅读完整计算与理由。

AB=[[58,64],[139,154]],形状为 2×2。

04为什么这个方法成立

  1. 固定 i、j,内部循环累计了前 p 项内积;初始为 0,每次加入下一项,保持这个不变量。
  2. 内层结束时包含全部 k 项,因此得到定义中的 Cᵢⱼ。
  3. 外层遍历每个合法 i、j,所以所有输出元素恰好计算一次。

05把推导翻译成代码

Python · 可独立运行的教学实现

def matmul(A,B):
    if not A or not B or not A[0] or not B[0]:
        raise ValueError("nonempty matrices required")
    m,k,n = len(A),len(A[0]),len(B[0])
    if any(len(row)!=k for row in A) or len(B)!=k or any(len(row)!=n for row in B):
        raise ValueError("incompatible rectangular shapes")
    C = [[0 for _ in range(n)] for _ in range(m)]
    for i in range(m):
        for j in range(n):
            for p in range(k):
                C[i][j] += A[i][p]*B[p][j]
    return C

print(matmul([[1,2,3],[4,5,6]],[[7,8],[9,10],[11,12]]))

逐个理解关键决定

len(B)!=k
左矩阵列数必须等于右矩阵行数。
for _ in range(m)
为每一行分别创建列表,避免 [[0]*n]*m 的别名问题。
C[i][j] += A[i][p]*B[p][j]
p 同时索引 A 的列和 B 的行,是被求和消去的维度。

06时间、空间与实现范围

经典实现时间 O(mkn),输出占 O(mn);除输出外只有循环变量的 O(1) 额外空间。

大整数乘加并非固定成本;浮点 BLAS 性能还受到数据布局和硬件吞吐影响。

07改变条件,检查哪里会出错

把 B[p][j] 写成 B[j][p]

那通常变成错误的索引或隐含转置。

看到三层循环就写 O(n³)

矩形输入应分别保留 m、k、n;只有同阶方阵才简化为 O(n³)。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

3×4 乘 4×5 得到什么形状?

需要一点提示

保留外侧维度。

查看解析与答案

3×5,每个元素累加 4 项。

练习 2 · 边界与辨析

2×3 与 2×3 能直接做矩阵乘法吗?

需要一点提示

比较内侧维度 3 和 2。

查看解析与答案

不能;逐元素乘法是另外一种操作。

练习 3 · 变式与迁移

为什么乘单位矩阵不改变 A?

需要一点提示

每列仅一个位置为 1。

查看解析与答案

内积只选出对应的 A 元素,其他项都乘 0。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

NVIDIA · CUDA Best Practices Guide

理解之后,继续递进

继续当前专题:分块 →。跨专题先修要求会在下一课顶部提示。

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。