矩阵乘法

概述

矩阵乘法（Matrix Multiplication）是线性代数和算法中的基本运算。两个 $n\times n$ 矩阵相乘的朴素算法时间复杂度为 $\Theta (n^3)$。通过Strassen 算法等分治方法可优化至 $O(n^{2.81})$，Coppersmith-Winograd 算法进一步优化至 $O(n^{2.376})$。矩阵乘法在图算法（如 Floyd-Warshall）和线性方程组求解中有重要应用。

定义

矩阵乘法（Matrix Multiplication）

给定两个 $n\times n$ 矩阵 $A$ 和 $B$，其乘积 $C=A\times B$ 也是一个 $n\times n$ 矩阵，其中：

$C_{ij}={\sum }_{k=1}^n{A}_{ik}\cdot B_{kj}$

朴素算法需要计算 $n^2$ 个元素，每个元素需要 $n$ 次乘法和 $n-1$ 次加法，总时间复杂度为 $\Theta (n^3)$。

核心性质

性质	描述	备注
不满足交换律	$AB\ne BA$（一般情况）	与标量乘法不同
满足结合律	$(AB)C=A(BC)$	可以任意改变计算顺序
分配律	$A(B+C)=AB+AC$	矩阵乘法对加法的分配律
朴素复杂度	$\Theta (n^3)$	三重循环的基本实现
Strassen 优化	$O(n^{\lg 7})\approx O(n^{2.81})$	分治方法，减少乘法次数
理论最优	$O(n^{2.373})$（2023 年最新结果）	实际应用中仍常用朴素或 Strassen

算法复杂度对比

算法	时间复杂度	特点
朴素算法	$\Theta (n^3)$	实现简单，常数因子小
Strassen	$O(n^{2.81})$	分治法，$n$ 较大时优于朴素
Coppersmith-Winograd	$O(n^{2.376})$	理论突破，实际不实用
最新理论结果	$O(n^{2.373})$	纯理论意义

应用场景

• 图的最短路径：Floyd-Warshall 算法本质上是矩阵乘法的变体（$(\min ,+)$ 半环上的矩阵乘法）
• 线性方程组求解：$Ax=b$ 的求解涉及矩阵运算
• 计算机图形学：变换矩阵的复合（旋转、缩放、平移）
• 机器学习：神经网络的前向传播本质上是矩阵乘法
• 密码学：某些加密算法使用矩阵运算

参见

• Strassen算法 — 分治法优化的矩阵乘法
• 分治法 — Strassen 算法的设计策略
• 矩阵 — 矩阵的基本概念和运算
• 动态多线程 — 并行矩阵乘法