矩阵乘法分治法.docx
《矩阵乘法分治法.docx》由会员分享，可在线阅读，更多相关《矩阵乘法分治法.docx（13页珍藏版）》请在冰点文库上搜索。
矩阵乘法分治法
算法设计与分析实验报告
实验名称：
矩阵乘法（分冶法）
一、问题陈述和分析：
1.实验目的：
掌握分总冶策略的基本思想以及用分冶法解决问题的一般技巧．运用编程工具，并运用分冶法来解决矩阵乘法问题；
2.实验内容：
设A和B是两个n*n阶矩阵，求它们两的乘积矩阵C。
这里，假设n是2的幂次方；
3.实验要求：
编制程序并对其时间复杂度和空间复杂度进行分析.
二、模型拟制、算法设计和正确性证明：
设A和B是两个n*n阶矩阵，求他们两的成绩矩阵C。
这里假设n是2的幂次方；
A和B是两个n*n的矩阵，他们的乘积C=AB也是一个n*n的矩阵，矩阵C中的元素C[i][j]定义为C[i][j]=
，则每计算一个C[i][j]，需要做n次乘法和n-1次加法。
因此计算C的n2个元素需要n3次乘法和n3-n2次加法。
因此，所需的时间复杂度是O（n3）。
但是使用分治法可以改进算法的时间复杂度。
这里，假设n是2的幂。
将矩阵A,B,C中每一矩阵都分成4个大小相等的子矩阵，每个子矩阵是（n/2）*（n/2）的方阵。
由此，可将方阵C=AB重写为
因此可得：
C11=A11B11+A12B21
C12=A11B12+A12B22
C21=A21B11+A22B22
C22=A21B12+A22B22
这样就将2个n阶矩阵的乘积变成计算8个n/2阶矩阵的乘积和4个n/2阶矩阵的加法。
当n=1时，2个1阶方阵的乘积可直接算出，只需要做一次乘法。
当子矩阵阶n>1时，为求两个子矩阵的乘积，可继续对两个子矩阵分块，直到子矩阵的阶为1。
由此，便产生了分治降阶的递归算法。
但是这个算法并没有降低算法的时间复杂度。
由strassen矩阵乘法，
M1=A11（B12-B22）
M2=（A11+A12）B22
M3=（A21+A22）B11
M4=A22（B21-B11）
M5=（A11+A22）（B11+B22）
M6=（A12-A22）（B21+B22）
M7=（A11-A21）（B11+B12）
C11=M5+M4-M2+M6
C12=M1+M2
C21=M3+M4
C22=M5+M1-M3-M7
算法共进行7次举证乘法，算法效率得到降低
主要数据的定义：
intn；n是方阵A,B,C的阶
int**A=newint*[n];//矩阵A，B，C的定义，并为它们分配空间。
这里A，B是用//于相乘的矩阵，C用于存放AB的结果
int**B=newint*[n];
int**C=newint*[n];
inti,j;
for（i=0;i{
A[i]=newint[n];
B[i]=newint[n];
C[i]=newint[n];
}
程序中定义的函数：
1.voidDivide（intn,int**A,int**A11,int**A12,int**A21,int**A22）
函数实现的功能是：
将n*n的矩阵A分块成四个大小相等的（n/2）*（n/2）的子矩阵A11,A12,A21,A22。
2.voidUnit（intn,int**A,int**A11,int**A12,int**A21,int**A22）
函数实现的功能是：
将四个（n/2）*（n/2）的矩阵A11,A12,A21,A22合并成一个n*n的矩阵A。
4.voidAdd（intn,int**A,int**B,int**C）
函数的功能是：
实现C=A+B，A，B，C都是n*n矩阵。
3.voidMul（intn,int**A,int**B,int**M）
函数的功能是：
将n*n的矩阵A，B相乘，结果存放在n*n的矩阵M中。
算法设计：
整个算法的大致思想是：
在函数Mul（intn,int**A,int**B,int**M）中先判断n的值，若n==1，表示A，B，C均为一阶方阵。
则M[0][0]=A[0][0]*B[0][0]；否则，调用Divide（n,A,A11,A12,A21,A22）;和Divide（n,B,B11,B12,B21,B22）;将A和B都分为四个（n/2）*（n/2）的子矩阵。
然后递归调用
Sub（n,B12,B22,T1）;T1=B12-B22
Mul（n,A11,T1,M1）;M1=A11（B12-B22）
Add（n,A11,A12,T2）;
Mul（n,T2,B22,M2）;M2=（A11+A12）B22
Add（n,A21,A22,T1）;
Mul（n,T1,B11,M3）;M3=（A21+A22）B11
Sub（n,B21,B11,T1）;
Mul（n,A22,T1,M4）;M4=A22（B21-B11）
Add（n,A11,A22,T1）;
Add（n,B11,B22,T2）;
Mul（n,T1,T2,M5）;M5=（A11+A22）（B11+B22）
Sub（n,A12,A22,T1）;
Add（n,B21,B22,T2）;
Mul（n,T1,T2,M6）;M6=（A12-A22）（B21+B22）
Sub（n,A11,A21,T1）;
Sub（n,B11,B12,T2）;
Mul（n,T1,T2,M7）;M7=（A11-A21）（B11+B12）
Add（n,M5,M4,T1）;
Sub（n,T1,M2,T2）;
Add（n,T2,M6,M11）;M11=M5+M4-M2+M6
Add（n,M1,M2,M12）;M12=M1+M2
Add（n,M3,M4,M21）;M21=M3+M4
Add（n,M5,M1,T1）;
Sub（n,T1,M3,T2）;
Sub（n,T2,M7,M22）;M22=M5+M1-M3-M7
Unit（n,M,M11,M12,M21,M22）;
将上面得到的四个矩阵组合成一个n*n矩阵。
则这个n*n矩阵就是AB的结果C。
正确性证明：
由矩阵乘法的计算方法可知，上述计算方法显然正确
三、时间和空间复杂性分析：
时间复杂性：
Strassen矩阵乘法中，用了7次对于n/2阶矩阵乘法的递归调用和18次n/2阶矩阵的加减运算。
由此可知，该算法所需的计算时间T（n）满足如下递归方程
解此递归方程得
。
由此可见，strassen矩阵乘法的计算时间复杂性比普通乘法有较大改进。
空间复杂性：
程序中定义了一些整型变量和若干个二维数组。
因此算法的时间复杂度是O（n*n）。
四、程序实现和测试过程：
程序测试过程
（1）
测试过程
（2）
五、总结：
源程序：
#include
#include
#include
usingnamespacestd;
ifstreaminfile（"123.txt",ios:
:
in）;
voidInput（intn,int**A）
{
//infile>>n;
for（inti=0;ifor（intj=0;jinfile>>A[i][j];
}
voidOutput（intn,int**A）
{
for（inti=0;i{
for（intj=0;jcout<cout<}
cout<}
voidDivide（intn,int**A,int**A11,int**A12,int**A21,int**A22）
{
inti,j;
for（i=0;ifor（j=0;j{
A11[i][j]=A[i][j];
A12[i][j]=A[i][j+n];
A21[i][j]=A[i+n][j];
A22[i][j]=A[i+n][j+n];
}
}
voidUnit（intn,int**A,int**A11,int**A12,int**A21,int**A22）
{
inti,j;
for（i=0;ifor（j=0;j{
A[i][j]=A11[i][j];
A[i][j+n]=A12[i][j];
A[i+n][j]=A21[i][j];
A[i+n][j+n]=A22[i][j];
}
}
voidSub（intn,int**A,int**B,int**C）
{
inti,j;
for（i=0;ifor（j=0;jC[i][j]=A[i][j]-B[i][j];
}
voidAdd（intn,int**A,int**B,int**C）
{
inti,j;
for（i=0;ifor（j=0;jC[i][j]=A[i][j]+B[i][j];
}
voidMul（intn,int**A,int**B,int**M）
{
if（n==1）
M[0][0]=A[0][0]*B[0][0];
else
{
n=n/2;
int**A11,**A12,**A21,**A22;
int**B11,**B12,**B21,**B22;
int**M11,**M12,**M21,**M22;
int**M1,**M2,**M3,**M4,**M5,**M6,**M7;
int**T1,**T2;
A11=newint*[n];
A12=newint*[n];
A21=newint*[n];
A22=newint*[n];
B11=newint*[n];
B12=newint*[n];
B21=newint*[n];
B22=newint*[n];
M11=newint*[n];
M12=newint*[n];
M21=newint*[n];
M22=newint*[n];
M1=newint*[n];
M2=newint*[n];
M3=newint*[n];
M4=newint*[n];
M5=newint*[n];
M6=newint*[n];
M7=newint*[n];
T1=newint*[n];
T2=newint*[n];
inti;
for（i=0;i{
A11[i]=newint[n];
A12[i]=newint[n];
A21[i]=newint[n];
A22[i]=newint[n];
B11[i]=newint[n];
B12[i]=newint[n];
B21[i]=newint[n];
B22[i]=newint[n];
M11[i]=newint[n];
M12[i]=newint[n];
M21[i]=newint[n];
M22[i]=newint[n];
M1[i]=newint[n];
M2[i]=newint[n];
M3[i]=newint[n];
M4[i]=newint[n];
M5[i]=newint[n];
M6[i]=newint[n];
M7[i]=newint[n];
T1[i]=newint[n];
T2[i]=newint[n];
}
Divide（n,A,A11,A12,A21,A22）;
Divide（n,B,B11,B12,B21,B22）;
//cout<<"A11,A12,A21,A22"<//Output（n,A11）;Output（n,A12）;Output（n,A21）;Output（n,A22）;
Sub（n,B12,B22,T1）;
//cout<<"B12-B22"<//Output（n,T1）;
Mul（n,A11,T1,M1）;
Add（n,A11,A12,T2）;
Mul（n,T2,B22,M2）;
Add（n,A21,A22,T1）;
Mul（n,T1,B11,M3）;
Sub（n,B21,B11,T1）;
Mul（n,A22,T1,M4）;
Add（n,A11,A22,T1）;
Add（n,B11,B22,T2）;
Mul（n,T1,T2,M5）;
Sub（n,A12,A22,T1）;
Add（n,B21,B22,T2）;
Mul（n,T1,T2,M6）;
Sub（n,A11,A21,T1）;
Add（n,B11,B12,T2）;
Mul（n,T1,T2,M7）;
Add（n,M5,M4,T1）;
Sub（n,T1,M2,T2）;
Add（n,T2,M6,M11）;
Add（n,M1,M2,M12）;
Add（n,M3,M4,M21）;
Add（n,M5,M1,T1）;
Sub（n,T1,M3,T2）;
Sub（n,T2,M7,M22）;
Unit（n,M,M11,M12,M21,M22）;
}
}
intmain（）
{
intn;
cout<<"pleaseinputnumbern"<cin>>n;
int**A,**B,**C;
A=newint*[n];
B=newint*[n];
C=newint*[n];
for（inti=0;i{
A[i]=newint[n];
B[i]=newint[n];
C[i]=newint[n];
}
Input（n,A）;
cout<<"AMatrixis"<Output（n,A）;
Input（n,B）;
cout<<"BMatrixis"<Output（n,B）;
Input（n,C）;
//Output（n,C）;
Mul（n,A,B,C）;
cout<<"TheProductofAandBis"<Output（n,C）;
//cout<in（）;
return0;
}
升级会员 