矩阵乘法是将一个 矩阵 与一个 矩阵 相乘,得到一个 矩阵 的运算。乘积矩阵中的每个元素,都是 的某一行与 的某一列中对应元素的乘积之和。与普通的数的乘法不同,矩阵乘法的结果取决于因子的顺序: 和 可能不同,而且其中一个可能有定义,另一个却没有定义。
矩阵乘法的定义法则是线性代数的基础,因为它在坐标表示下刻画了线性变换的复合。同一运算也可用于描述连续施加的几何变换、网络中的传播、坐标变换,以及多组变量之间的相互作用。矩阵乘法还是一种核心计算操作:科学模拟、统计估计和机器学习中的大量计算,都可以围绕矩阵乘积来组织。
因此,矩阵乘法兼具代数与计算两方面的特征。它的代数性质解释了变换如何复合,而它的算法则涉及算术复杂度、数值误差、数据搬移和并行执行等问题。通常所说的行列相乘运算,还必须与数组上的其他运算区分开来,包括逐元素乘积和张量积。
定义与行列相乘法则
设 有 行、 列, 有 行、 列。它们的乘积 定义为
相匹配的维数 决定了计算结果中每个元素时需要累加的项数。外侧的维数 和 则决定结果的形状。因此,一个 矩阵可以乘以一个 矩阵,得到一个 矩阵,但反过来的乘积没有定义。两个矩阵形状相同,既不是它们的普通乘积有定义的必要条件,也不是充分条件。
例如,
左上角的元素为 。其余各元素也都按同一法则独立计算。一个行矩阵乘以一个列矩阵,得到一个 矩阵,通常将其与其中的标量元素视为同一对象。而一个列矩阵乘以一个行矩阵,得到的通常是一个更大的矩阵,称为外积。
在实数范围内,将 的一行和 的一列都视为向量,就可以把结果中的一个元素解释为这两个向量的内积。在复数范围内,这种说法需要谨慎使用:普通矩阵乘法不会对任何一个因子取共轭,而标准的复内积会对其中一个自变量取共轭。因此,更准确地说,普通矩阵乘法采用的是行与列之间的双线性配对。
矩阵的元素通常取自一个域,例如实数域或复数域,但这一定义同样适用于环上的矩阵。如果标量乘法不满足交换律,就必须保持 的顺序。许多熟知的矩阵恒等式仍然成立,不过其中一些恒等式,例如通常的乘积转置恒等式,需要对标量作额外假设。
矩阵乘法不同于标量乘法,后者只是将每个元素都乘以同一个数。它也不同于逐元素乘法,后者要求两个矩阵形状相同,而且不涉及沿共同维度求和。正是行与列相乘后求和这一规则,使普通矩阵乘法能够描述经由一组中间坐标的变换过程。
线性映射的复合与几何意义
矩阵乘法最核心的含义是线性映射的复合。设 和 是有限维向量空间之间的线性映射。在各个空间中选定一组基后,设 表示 , 表示 。那么,复合映射 就由 表示:
这里的方括号表示坐标列向量。最右侧的矩阵最先作用。这一约定既解释了维数为何必须匹配,也解释了各因子的排列顺序:第一个变换的输出坐标必须与第二个变换的输入坐标相匹配。
矩阵的各列记录了输入空间中各基向量的像。若 的各列为 ,则
因此,左乘 就是对 的每一列施加同一个变换。等价地,乘积的第 列是 的各列的线性组合,其系数取自 的第 列。与逐个计算矩阵元素相比,这种视角往往更能揭示矩阵乘法的含义。
几何变换可以说明顺序为何重要。考虑逆时针旋转 的变换,
以及水平方向的拉伸变换,
于是
先拉伸后旋转与先旋转后拉伸的结果不同,因为拉伸是沿特定坐标方向进行的。因此,不可交换性是一种几何特征,而不只是记号上的特殊之处。
基的变换也涉及矩阵乘积。如果可逆矩阵 将新基下的坐标转换为旧基下的坐标,那么,在旧基下由 表示的算子,在新基下就由下式表示:
这种关系称为矩阵相似。它改变了算子的坐标表示,却保留了算子的内在性质,包括其特征值。借助矩阵乘法,我们可以将映射本身与用来表示它的数值矩阵区分开来。
平移不是普通坐标向量上的线性映射,但利用齐次坐标,也可以将其纳入矩阵表示。平面上的仿射映射可以用一个作用于 的 矩阵来表示。这些矩阵的乘积能够以统一的记法组合平移、旋转、缩放和剪切,这是计算机图形学和几何建模中的标准方法。
代数法则及其局限
只要矩阵的维数允许相乘,矩阵乘法就满足结合律:
将两边展开并调整有限求和的次序,即可得到这一结论。用矩阵元素表示时,两边都化为
结合律使 这样的表达式具有明确的含义,尽管不同的括号分组方式可能导致计算成本相差很大。它也反映了变换复合的结合律。
矩阵乘法对加法满足分配律:
对于通常的标量域,标量因子可以在乘积中移动:
对于 矩阵 ,相应的单位矩阵满足 。因此,固定阶数的方阵构成一个结合代数。然而,矩阵乘法一般不满足交换律,乘以非零矩阵也未必能约去。
特别地, 并不意味着其中任何一个因子为零。例如,
第一个因子将第二个因子的像中的每个向量都映为零。更一般地, 当且仅当 的像包含于 的核。这与线性映射的像和核之间的联系,解释了熟悉的标量消去律为何在这里失效。
当方阵可逆时,
次序的颠倒至关重要:要撤销一连串操作,必须先撤销最后一步。逆矩阵使消去律重新成立,因此,若 可逆,则由 可得 。对于交换域上的矩阵,矩阵转置和共轭转置同样会颠倒乘积中因子的次序:
若干数值不变量满足重要的乘积恒等式。对于同阶方阵,
因此,行列式将矩阵乘积转化为标量乘积。对于大小为 的 和大小为 的 ,矩阵的迹满足 ,即使这两个乘积的大小可能不同。矩阵的秩满足
复合映射所能产生的独立输出方向,不可能多于任一因子所能传递的独立方向。相比之下,乘积的特征值一般不能通过将各因子的对应特征值相乘而得到;这类公式需要额外的结构,例如具有一组共同的特征向量基。
分块乘积、缩并与其他乘积
矩阵可以划分为若干矩形分块,然后在分块层面进行乘法运算。例如,
分块方式必须相容:每对相乘分块的内维数必须匹配。各个分块不必是方阵,大小也不必相同。这个公式仍然遵循行列相乘求和的规则,只是将元素换成了矩阵,并保留各分块因子的相乘顺序。分块记法有助于推导证明、构建结构化数值方法,以及设计对快速存储器中的小型子矩阵进行运算的算法。
另一种有用的分解是将乘积写成外积之和。若 是 的第 列, 是 的第 行,则
每一项的秩至多为一。这种表示是秩一更新的基础,也直接解释了为什么结果的秩不会超过两个矩阵共有的内维数。由此还可以自然地得到每次累加一个秩一项的算法。
在张量记法中,矩阵乘法是对一个共有指标进行的张量缩并。按照爱因斯坦求和约定,可以省略求和符号,将乘积写成 ,其中重复出现的指标 隐含表示对其求和。高维数组运算通常通过指定要缩并的轴来推广这一模式。其确切行为取决于所采用的指标约定;任意一种多维数组乘积并不一定就是普通矩阵乘法。
还有两种乘积必须与普通矩阵乘积区分开来。阿达玛积将形状相同的矩阵按对应元素相乘:
克罗内克积将每个元素 替换为分块 ;当 为 矩阵、 为 矩阵时,得到的是一个 矩阵。它表示线性映射的张量积在乘积基下的矩阵。这些运算有着不同的维数规则和数学含义。
行列相乘求和的构造还可以从普通算术推广到半环。对于布尔值元素,用逻辑或代替加法、用逻辑与代替乘法,得到的输出就能指示是否存在至少一条经由中间节点的连接。在最小值加法运算中,加法被替换为取最小值,乘法被替换为普通加法。所得元素 表示费用最低的两阶段路径。这类推广保留了矩阵乘法的组织形式,同时改变了各累加项的含义。
经典算法与矩阵链乘法
直接算法用三重嵌套循环实现矩阵乘法的定义。对于一个 矩阵与一个 矩阵相乘,它需要执行 次标量乘法;若每个输出元素都从第一项开始累加,则还需要执行 次标量加法。对于 阶方阵,若将一次乘法和一次加法各计为一次运算,则总计约需 次浮点运算。因此,在每次算术运算成本均为常数的模型下,其运行时间用大O记号表示为 。
三个下标可以按不同顺序遍历,而不改变精确的数学结果。按 顺序遍历时,可以逐个计算输出元素;按 顺序遍历时,则可以在更新输出矩阵中一段连续元素的同时,重复使用左侧矩阵的某个元素。哪种顺序性能最佳,取决于数据布局和存储器体系结构。调整遍历顺序也会改变浮点数的求和顺序,因此,代数上等价的程序未必会产生逐位相同的结果。
结合律使矩阵连乘产生了另一个优化问题。若 的大小为 , 为 , 为 ,则计算 需要
次标量乘法。计算 则需要
两者的输出在数学上完全相同,但算术运算次数相差十倍。矩阵链乘法问题利用动态规划,为给定的矩阵维度序列选择最优的括号化方案。它改变的是各因子的分组方式,而不是它们的排列顺序。
利用矩阵结构可以大幅降低计算成本。与对角矩阵相乘,只需对行或列进行缩放;与置换矩阵相乘,则只需重新排列行或列。对于稀疏矩阵 ,计算 与一个有 列的稠密矩阵的乘积时,通常可以围绕已存储的非零元素组织运算;除去输出初始化和索引开销,所需工作量与 成正比。两个稀疏矩阵相乘更为复杂,因为还必须确定乘积中非零元素的位置,而且结果可能比任一输入矩阵都稠密得多。
低秩结构提供了另一种途径。若 ,其中内部维度 较小,则
这样可以避免显式构造完整矩阵 。因此,一种乘法算法是否实用,不仅取决于矩阵维度,还取决于稀疏性、秩、所需精度,以及是否必须显式存储乘积本身。
历史发展与快速乘法
现代矩阵乘法源于十九世纪对行列式和线性变换的研究。詹姆斯·约瑟夫·西尔维斯特于1850年引入了“矩阵”一词。阿瑟·凯莱于1858年发表的论文《矩阵理论研究》推动了矩阵作为代数对象的确立:矩阵拥有自身的加法和乘法,而不再仅仅是与行列式相关的系数排列。矩阵乘法法则体现了变换的复合,也表明具有实用价值的代数可以是非交换的。
此后约一个世纪的大部分时间里,标准的立方时间算法似乎就是矩阵乘法定义在计算上的自然实现。决定性的转变发生在1969年:沃尔克·施特拉森证明,两个 分块矩阵相乘,只需进行七次而非八次分块乘法,代价是增加一些分块加法和减法。递归应用这一恒等式,可得递推关系
因此有
这是首次得到广泛认可的证明,表明一般矩阵乘法所需算术运算次数不必达到立方量级。
施特拉森算法的关键特点在于,它计算的是矩阵元素的组合,而不是独立计算每个输出元素所对应的点积。对于
其七个中间乘积中的两个是 和 。通过精心选择对这七个乘积所做的加减运算,可以还原出四个输出元素。将这些恒等式应用于矩阵块时,它们仍然成立,因为其中的乘法顺序保持不变。在实际实现中,通常会在分块大小适中时停止递归,转而使用常规乘法内核。
后续研究将矩阵乘法与双线性张量的分解联系起来。矩阵乘法指数通常记为 ,其定义为所有满足以下条件的指数 的下确界:在所考察的域上,方阵相乘可以用 次算术运算完成。基本界为 ;其中,下界反映了标准显式模型中输入和输出的规模。施特拉森证明了 ,而唐·科珀史密斯与施穆埃尔·维诺格拉德于1990年的研究则将上界降至 以下。此后的研究进一步降低了上界,但 是否成立仍是未解问题。
渐近意义上更小的指数,并不保证在实际规模下计算更快。常数因子、临时存储、通信、矩形矩阵的形状以及数值表现都很重要。有些理论方法只有在维数极其庞大时才显出优势,还有一些方法虽然确立了复杂度界,却无法据此得到具有竞争力的实现。因此,理论算术复杂度研究与实际的高性能矩阵乘法虽有交集,却并非同一个优化问题。
浮点误差与数值可靠性
精确的矩阵恒等式在计算机上并不一定严格成立。在浮点运算中,一次基本运算通常用以下模型表示:
其中, 是单位舍入误差。这一相对误差模型假定不会发生上溢,也不会出现影响模型成立的下溢。由于矩阵乘法包含大量标量乘法和加法,计算得到的各个元素都会累积舍入误差。
对于常规的点积计算,标准的逐元素误差估计为
前提是 ,且通常的算术假设成立。这里的绝对值和不等式均按元素理解,而 本身是普通的矩阵乘积。这一界限的重要之处在于,它取决于各项贡献的大小,而不只是最终结果的大小。
因此,相消可能使数值较小的输出元素产生较大的相对误差。如果正项和负项几乎相互抵消,那么即使 很大, 也可能非常小。此时,一个很小的绝对舍入误差,相对于精确结果而言也可能很大。这也体现了数值稳定性与数学问题的条件性之间的区别:前者关注算法的行为,后者关注问题对数据扰动的敏感程度。
实现中的多种选择都会影响误差。与长串的顺序求和相比,成对求和可以降低累加的深度。补偿求和则保留了原本会因舍入而丢失的信息。融合乘加指令计算一个乘积与累加值之和时,只在最后进行一次舍入,而不是分别对乘法和加法进行舍入。这些方法在计算成本与精度之间各有取舍。并行归约也可能改变各项的分组方式,使不同的线程数或执行调度产生略有差异的结果。
混合精度乘法对输入或乘法运算使用一种数值格式,而对累加使用另一种通常位宽更大的格式。这可以显著提高吞吐量,但精度取决于输入量化、累加精度以及前后相关的计算。位宽更大的累加器无法恢复输入转换为较低精度格式时已经丢失的信息。
快速递归算法需要单独进行误差分析,因为它们引入了额外的加减运算,并且可能产生比最终结果更大的中间值。不能一概认定 Strassen 类方法在数值上不可用,但递归深度、缩放方式和误差常数都很重要。在数值线性代数中,恰当的评估通常应关注它们对完整任务的影响,例如求解方程组或进行矩阵分解,而不应只测量一次孤立矩阵乘法的耗时或误差。
存储层次结构、程序库与并行执行
对于大型稠密矩阵,性能既取决于算术运算,也同样取决于数据搬移。处理器通常具有由寄存器、高速缓存和主存构成的存储层次结构,各层容量依次增大,访问速度依次降低。朴素实现可能反复从慢速存储器中加载相同的元素。分块算法则将矩阵划分为若干子块,在替换已加载的数据之前,利用这些数据执行多次算术运算。
一种常见实现围绕以下形式的更新来组织计算:
其中, 标识各个分块。经过优化的软件通常会将选定的面板复制或“打包”到连续缓冲区中,并调用一个小型微内核,将部分输出保存在寄存器中。打包会带来额外开销,但它对内存对齐、向量化和数据复用的改善,可能足以抵消这部分成本。分块大小的选择取决于处理器和存储层次结构,而不只是代数层面的考量。
基本线性代数子程序接口通常简称为 BLAS,它对广泛使用的数值计算内核进行了标准化。其中的通用矩阵乘法运算 GEMM 计算:
其中, 可以保持矩阵不变,也可以对矩阵进行转置或共轭转置。该接口将乘法、缩放和累加合并在一起,无须分别生成与结果同等大小的临时矩阵。GEMM 属于三级 BLAS 运算,这意味着它以矩阵为操作对象,而不是主要处理单个向量。
稠密矩阵乘法尤其适合现代并行硬件,因为相对于所存储的数据量,它需要执行大量算术运算。多核处理器可以将不同的输出子块分配给不同线程。图形处理器能够并发执行大量小规模运算,而专用矩阵运算单元则执行固定大小的分块乘加运算。批量矩阵乘法将许多小矩阵乘法合并到一次执行请求中,既降低了开销,也挖掘出单个小矩阵无法提供的并行性。
在分布式内存系统中,矩阵被划分并分配给各个进程,进程之间通过交换面板或分块来计算各自的局部输出。通信开销既涉及消息数量,也涉及传输数据的总量。二维块循环分布将矩阵的各个区域分散到进程网格中,同时实现工作负载均衡。通过额外复制数据,某些算法有时能够进一步减少通信,但代价是占用更多内存。
这些制约因素解释了为什么仅凭算术运算次数无法预测实际运行时间。使标量乘法次数最少的方法,可能需要搬移更多数据、分配更多临时存储空间,或进行更频繁的同步。高性能实现需要在算术吞吐量、存储容量、通信和数值要求之间取得平衡。其性能表现还取决于矩阵是方阵、行数远多于列数、列数远多于行数、稀疏矩阵,还是规模小到使准备开销占据主导地位的矩阵。
在统计学、学习、网络与动力学中的应用
在统计学中,矩阵乘法可以同时表示多个观测与变量之间的关系。如果数据矩阵 的行对应观测、列对应变量,那么 就汇集了各变量两两之间的乘积之和。对各列进行中心化并适当缩放后,便可得到样本协方差矩阵。对于系数向量为 的线性模型,乘积 给出其拟合值。普通最小二乘法的正规方程为
尽管这些方程在理论上具有核心地位,但数值求解器通常采用QR分解或奇异值分解,而不是显式构造 来求解,因为构造该矩阵可能使问题的条件性变差。
其中, 的各行包含输入样本, 包含权重, 包含偏置。将多个样本一起处理,就能把多次矩阵与向量的乘法转化为一次矩阵与矩阵的乘法。在自动微分过程中,与此密切相关的乘积用于计算相对于输入和参数的导数。在注意力机制中, 这样的乘积用于计算两两之间的分数,另一次乘法则将归一化后的分数与值向量组合起来。各矩阵的维度规定了哪些样本、位置或特征之间发生交互。
在图论中,设 为有限有向图的邻接矩阵,当顶点 到顶点 存在一条边时,。在通常的算术运算下, 表示从 到 、长度为 的有向游走的数量。这是对所有中间顶点求和的直接结果。在布尔运算下,相应的乘积记录的是是否存在这样的游走,而非其数量。因此,矩阵乘积将局部的边信息与多步连通性联系起来。
马尔可夫链以概率使用同样的结构。在采用行向量的约定下,概率分布按 演化,其中 是转移矩阵。 的各元素给出 步转移概率。对中间状态求和,恰好就是矩阵乘法的法则,体现了将经过这些状态的互斥路径的概率相加。
矩阵的幂和乘积还用于描述离散动力系统、控制模型和数值演化方程。对于常矩阵 ,线性微分方程 的解涉及矩阵指数,其定义为
在计算物理与工程领域,离散化会产生大型方程组,其组装、分解和反复求解都依赖矩阵乘积。在量子力学中,算符矩阵的乘积表示对状态依次施加的变换。在这些应用中,重复指标始终具有相同的运算含义:对经过一组中间坐标、状态或自由度的贡献求和。