斯坦福 CS367 代数图算法讲义
需积分: 5 158 浏览量
2024-02-01
14:41:36
上传
评论
收藏 1.42MB PDF 举报
第1讲和第2讲 矩阵乘法与矩阵求逆
记录员：Jessica Su 日期：2015年9月25日
编辑：Kathy Cooper
这门课程是关于矩阵乘法及其在图算法中的应用。
1 矩阵乘法的先前工作
定义1.1. (矩阵乘法) 设A和B是n×n矩阵（其中的元素有O(logn)位）。
那么乘积C，其中AB=C，是一个n×n矩阵，定义为([i, j]) =
∑
n
k
=
1
A(i,
k
)B(
k
, j)。
我们将假设在O(logn)位整数上的操作（加法和乘法）需要O(1)的时间，即我们将在一个字-RAM计算模
型中工作，字大小为O(logn)。
为了改进矩阵乘法的运行时间，已经做出了很多努力。 简单的算法在O( n^
3
)的时间内进行矩阵乘法。
斯特拉森（'69）通过提供一个O( n^
2.81
)的时间复杂度的算法，让所有人都感到惊讶。
从那时起，一系列的改进开始了，直到1986年，科波斯密斯和维诺格拉德实现了O(n^
2.37
6)的时间复杂度。
经过
2
4年的停滞，
2
010年爱丁堡大学的研究生安德鲁·斯托瑟改进了运行时间，将其降低到O(n^
2.37
4)。
2
0
11年，弗吉尼亚·威廉姆斯获得了O(n^
2.372
9)的时间复杂度，这是最好的界限，直到
2
014年勒·加尔获得了
O(n^
2.372
8
7
)的时间复杂度。 许多人相信最终的界限将是n^
2+
O(1)，但这尚未被证明。
今天我们将讨论矩阵求逆和矩阵乘法之间的关系。
2 矩阵乘法等同于矩阵求逆。
矩阵求逆很重要，因为它用于解线性方程组。 乘法等同于求逆，从某种意义上说，任何乘法算法都可以用
来得到一个类似运行时间的求逆算法，反之亦然。
2.1 乘法可以简化为求逆。
定理2.1. 如果可以在T( n)时间内求解n× n矩阵的逆，那么可以在O( T (3 n))时间内相乘n× n矩阵。
证明。设 A和 B为矩阵。假设
D =
I A 0
0 I B
0 0 I
其中 I是 n乘n的单位矩阵。 通过直接计算可以验证
D
−1
=
I −A AB
0 I −B
0 0 I
求逆 D的时间复杂度为 O(T (3n))，我们可以通过求逆 C来找到 AB。 注意 C始终可逆，因为其行列式
为1。
1
剩余33页未读，继续阅读
资源评论
