Strassen矩阵乘法[定义].pdf
版权申诉
152 浏览量
2021-10-12
00:48:00
上传
评论
收藏 126KB PDF 举报
实 验 报 告
一、实验目的
通过算法的程序实现和执行时间测试、 并与理论上的结论进行对比分析， 深
入理解算法时间复杂度分析中对于输入数据考虑其等价类的意义， 理解算法时间
复杂度渐进性态和和增长率的概念， 为后续学习和实验奠定基础， 同时也学习程
序效率测试的基本思路。
二、实验内容与实验步骤
（1）了解分治的基本思想并编写算法解决 Strassen 矩阵乘法问题。
（2）打开一台装有 MyEclipse-10.7.1 的 PC。
（3）把已经写好的代码在 Java 环境下运行并调试。
（4）记录运行结果。
三、实验环境
Windows 7 家庭普通版， MyEclipse-10.7.1
四、阐述 Strassen矩阵乘法
矩阵乘法是线性代数中最常见的运算之一，它在数值计算中有广泛的应用。
若 A 和 B 是 2 个 n×n 的矩阵，则它们的乘积 C=AB同样是一个 n×n 的矩阵。 A
和 B 的乘积矩阵 C中的元素 C[i,j] 定义为 :
若依此定义来计算 A 和 B 的乘积矩阵 C，则每计算 C 的一个元素 C[i,j] ，需
要做 n 个乘法和 n-1 次加法。因此，求出矩阵 C的 n2 个元素所需的计算时间为
0(n3) 。60 年代末，Strassen 采用了类似于在大整数乘法中用过的分治技术， 将
计算 2 个 n 阶矩阵乘积所需的计算时间改进到 O(nlog7)=O(n2.18) 。
五、问题分析
首先，我们还是需要假设 n 是 2 的幂。将矩阵 A，B 和 C中每一矩阵都分块
成为 4 个大小相等的子矩阵，每个子矩阵都是 n/2 ×n/2 的方阵。由此可将方程
C=AB重写为 :
课程名称 ：算法设计与分析 班级 ：12 软工一班 实验成绩 ：
实验名称 ：Strassen矩阵乘法 学号 ：1242159101 批阅教师签字：
实验编号 ：实验一 姓名 ：陈双飞 实验日期： 2014 年 12 月 14 日
指导教师 ：陈平 组号 ： 实验时间 ： 时 分－ 时 分
资源评论
czq131452007
- 粉丝: 2
- 资源: 12万+
下载权益
C知道特权
VIP文章
课程特权
VIP享7折，此内容立减4.47元 开通VIP
