矩阵乘法的Strassen算法(下)
2021/7/9 11:06:25
本文主要是介绍矩阵乘法的Strassen算法(下),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
上一节我们详细介绍了基本矩阵乘法和分治递归算法,详情可见”https://www.cnblogs.com/Bosson/p/14987366.html“。
这一节将详细介绍Strassen算法。
Strassen算法
Strassen算法目的是对分治递归算法的递归树进行剪枝,即从8次递归降为7次递归。
过程共有四个步骤:
-
- 将A、B、C各自分解为4个子矩阵(与前述相同)
- 创建10个同维度的矩阵Si(i = 1~10),每个矩阵Si保存A和B的8个子矩阵之间的和或差,需要花费O(n2)
- 利用上述的8个子矩阵和10个Si矩阵,递归计算7个矩阵积Pj,时间递归算法为T(n) = 7T(n/2) + O(n2),解为O(nlg7)
- 通过对Pj的不同组合进行加减运算,计算出矩阵C的4个子矩阵,需要花费O(n2)
接下来开始介绍Strassen算法的细节。
在步骤二中,我们需要创建10个Si矩阵如下所示:
S1 = B12 - B22
S2 = A11 + A12
S3 = A21 + A22
S4 = B21 - B11
S5 = A11 + A22
S6 = B11 + B22
S7 = A12 - A22
S8 = B21 + B22
S9 = A11 - A21
S10 = B11 + B12
在步骤三中,我们需要递归计算7次n/2 x n/2子矩阵的乘法,如下所示:
P1 = A11 x S1
P2 = S2 x B22
P3 = S3 x B11
P4 = A22 x S4
P5 = S5 x S6
P6 = S7 x S8
P7 = S9 x S10
在步骤四中,我们需要利用Pj矩阵进行加减法运算,计算出C的4个子矩阵,如下所示:
C11 = P5 + P4 - P2 + P6
C12 = P1 + P2
C21 = P3 + P4
C22 = P5 + P1 - P3 - P7
经过验算,可以发现C的4个子矩阵结果与分治递归算法中的结果是一致的。
总结
步骤三中递归式的解为O(nlg7),lg7 ≈ 2.81,即Strassen算法的渐进复杂性低于直接的矩阵乘法计算过程,是矩阵乘法的一种时间上改进的方法。
这篇关于矩阵乘法的Strassen算法(下)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?