Coppersmith-Winograd矩阵乘法算法解析
需积分: 12 169 浏览量
更新于2024-09-06
收藏 152KB PDF 举报
"这篇文档是关于矩阵乘法的，特别是Coppersmith-Winograd算法，由Matthew Anderson和Siddharth Barman在2009年12月6日撰写。文档涵盖了快速卷积算法，如Cook-Toom算法及其改进版、Winograd算法及其改进版，以及迭代卷积和循环卷积。它还讨论了设计快速卷积算法的方法，并对矩阵乘法的复杂度进行了深入探讨。"
文章的核心内容主要围绕以下几个知识点展开：
1. **矩阵乘法**：定义了一个矩阵乘法的概念，即给定两个矩阵A (m×n) 和B (n×p)，计算它们的乘积C (m×p)。对于平方矩阵（n=m=p）的讨论是主要焦点，但也可以扩展到不同尺寸的矩阵。
2. **Mk(n)**：定义了Mk(n)表示在域k上乘法操作的数量，以完成两个n×n矩阵的乘法。这个概念用于衡量不同算法的效率。
3. **ω(k)**：ω(k)定义为最小的指数，使得能用这个指数的多项式时间来完成n×n矩阵的乘法。简单来说，它是矩阵乘法运算复杂度的下界。
4. **矩阵乘法复杂度的历史发展**：文中提到了矩阵乘法算法的历史进步，从1969年的3（即传统的格子算法）到Coppersmith-Winograd算法的突破，这一系列的算法不断降低了矩阵乘法的理论时间复杂度。
5. **Cook-Toom算法和Modified Cook-Toom算法**：Cook-Toom算法是一种快速卷积方法，通过分解输入序列来减少乘法操作。其改进版本旨在进一步优化性能。
6. **Winograd算法和Modified Winograd算法**：Winograd算法是另一种著名的快速卷积方法，通过基本的算术操作组合来减少乘法的数量。同样，它的修改版也是为了提高效率。
7. **迭代卷积和循环卷积**：这两种方法是处理序列相关性的技术，特别是在信号处理和数字滤波器设计中。迭代卷积通过重复应用基本卷积操作来实现，而循环卷积则利用序列的周期性。
8. **快速卷积算法设计**：通过观察和分析，可以设计出更高效的卷积算法。这种方法通常涉及将大问题分解为小问题，然后重新组合解决方案。
这篇文档详细介绍了矩阵乘法的不同算法及其复杂度分析，尤其是Coppersmith-Winograd算法在降低矩阵乘法操作数量方面的贡献。这些算法和技术对于理解和优化计算密集型任务，如图形处理、数值模拟和机器学习等领域具有重要意义。
In particular, we get a linear map by holding the first entry of the bilinear map fixed, while
letting the second entry vary. Similarly if we hold the second entry fixed we again get a linear map.
For matrix multiplication U = V = W = F
n×n
, and we write this bilinear map as φ = hn, n, ni.
Definition 5 (rank). Let φ be a F-bilinear map. Then the rank of φ, R(φ) is the smallest r ∈ N
such that
φ(u, v) =
r
X
i
f
i
(u)g
i
(v)w
i
(4)
For w
i
∈ W and f and g are F-linear forms (a linear transformation from a vector space to its
scalar field).
The following proposition shows that R(hn, n, ni) is related to M(n):
Proposition 1 ([BCS97] Prop 15.1).
ω = inf{τ ∈ R|R(hn, n, ni) = O(n
τ
)}. (5)
Proof. Let the RHS in the statement of the proposition be θ and φ = hn, n, ni. Then
φ(a, b) =
|M(n)|
X
i
f
i
(a, b)g
i
(a, b)w
i
=
|M(n)|
X
i
(f
i
(a, 0) + f
i
(0, b))(g
i
(a, 0) + g
i
(0, b))w
i
=
|M(n)|
X
i
f
i
(a, 0)g
i
(0, b)w
i
+
|M(n)|
X
i
f
i
(0, b)g
i
(a, 0)w
i
(6)
The first step follows by bilinearity of φ and the second does also because the cross terms
f
i
(a, 0)g
i
(a, 0) and f
i
(0, b)g
i
(0, b) are not bilinear.
This shows that
1
2
R(hn, n, ni) ≤ M(n), which by the definition of ω immediately gives θ ≤ ω.
By definition of θ for > 0, there is some m > 1 such that r = R(hm, m, mi) ≤ m
θ+
. Then
there are linear forms f
i
, g
i
: K
m×m
→ K and matrices w
i
∈ K
m×m
. Such that for all A, B ∈ K
m×m
:
AB =
r
X
i
f
i
(A)g
i
(B)w
i
. (7)
However, K does not need to be a field (i.e. K = F); K could, in fact, be a matrix algebra:
K = F
m
i
×m
i
for some i ∈ N. Recall, an algebra over a field is a vector space equipped with a bilinear
vector product. Then two K matrices A and B can be multiplied over K using r multiplications
between elements of K, a number of additions between elements of K and some multiplications
between elements of F and elements of K.
Notice that K
m×m
' F
m
i+1
×m
i+1
, as F-algebras (block decomposition). This gives rise to the
following recurrence: M (m
i+1
) ≤ rM(m
i
)+cm
2i
, where c is proportional to the number of additions
and scalar multiplications used to compute f
i
and g
i
. Because c, m and r are constants, we can
solve this recurrence in terms of i, getting M(m
i
) = O(r
i
) (the multiplications are not easier than
addition and scalar multiplication).
Because M is monotone: M(n) = O(r
log
m
n
) = O(n
log
m
r
) = O(n
θ+
). This gives ω ≤ θ.
3
剩余10页未读，继续阅读
点击了解资源详情
点击了解资源详情
点击了解资源详情
2021-09-19 上传
2021-09-19 上传
2023-10-25 上传
