分裂与并行计算作业VIP

线性代数方程组串行与并行求解方法刘争光201311271问题考虑一般的线性方程组,最普遍的方法是先对做分解，其中为单位下三角阵，是上三角阵。于是方程组化为,率先求解这个三角形方程组，然后再求解。串行算法：（1）的分解采用部分选主元Gauss消去法进行列消元，使得L是单位下三角阵。算法中表示A的第K行。算法：forj=0,n-2选主元，找到如果fork=j+1,n-1endforendfor（2）流程图开始J=0，n-1找到每一列绝对值最大的元素作为主元，交换到A（j，j）处求解L，置于A的左下方即：高斯消去法求解U即：得到新的A，左下方为L，右上方为U结束（3）计算,解法类似。算法：fori=0,n-1forj=i+1,n-1endforendfor（4）流程图开始先由，得到然后消去第一列，得到新的右端项再按照得到的方法得到即结束并行算法LU分解算法：矩阵A采用卷帘方式存储，即把矩阵A的第i列存放在中。的算法如下：forj=0，n-2如果myid=mod(j,p),那么找到列主元素所在行选主元，找到如果把l和f广播给其他进程，为以后进行行交换icol=icol+1所有进程进行行交换即：如果fork=icol,m-1endforendfor流程图开始判断要执行语句的进程myid=mod(j,p)选主元得到进行行交换要用的元素l和f广播给每个进程所有进程进行行交换所有进程求解L和U结束结果（A的LU分解）分析：由于核数为2时，通信时间占据大部分并行时间，故效率很低。A的大小核数100*100160*160200*200串行8.0*10-31.6*10-23.2*10-2时间效率时间效率时间效率27.9*10-30.5061.2*10-20.662.8*10-20.5742.2*10-30.914.3*10-30.938.8*10-30.91附录串行程序：（1）!TheprogramistosolvetheequationAX=F!Thisisaserialprogram!subroutineinprogramnamedLUistosolveLUdecompositionforA!-----------------------------------------------------------------programmainimplicitnoneinterfacesubroutineLU(n,A,F)implicitnoneintegernreal::A(n,n),F(n)real::x(n),y(n)realmaxx,b,cendsubroutineendinterface!defineAisan*nmatrixinteger,parameter::n=80real::A(n,n),AA(n,n),F(n)integeri,jreal::x(n),y(n)realt1,t2!inordertofacilitate,wechooseAas!wheni=j,A(i,j)=0,elseA(i,j)=1!thenwechooseF(i)=n-1!soofcoursetheexactsolutionisx=(1)open(10,file="AAAA.txt")open(11,file="FFFF.txt")read(10,*)AAread(11,*)Fdoi=1,ndoj=1,nA(j,i)=AA(i,j)enddoenddocallcpu_time(t1)callLU(n,A,F)callcpu_time(t2)!getA=LU!firstly,solveLy=F!ofcourseLisaunderunittrianglematrixdoi=1,ny(i)=F(i)doj=i+1,nF(j)=F(j)-A(j,i)*y(i)enddoenddo!thensolveUx=y!ofcourseUisauptrianglematrixdoi=n,1,-1x(i)=y(i)/A(i,i)if(i>1)thendoj=i-1,1,-1y(j)=y(j)-A(j,i)*x(i)enddoendifenddo!thengetcputime!puttheresultXinANS.txtopen(12,file="ANS.txt")write(12,*)xwrite(*,*)"THECPU_TIMEIS:",t2-t1endprogram!ThissubroutineistosloveLUdecompositionforA!explainvariable!Aisthematrixwhichisgoingtodecomposite!FisAX=Ftherightitem!maxxisthemaxvalueofA(i,i)!--------------------------------------------------subroutineLU(n,A,F)implicitnoneintegernreal::A(n,n),F(n)realmaxx,b,cintegeri,j,l,kdoi=1,n-1maxx=abs(A(i,i))l=i!tofindthemaxabsolutevalueofeverycolumndoj=i+1,nif(abs(A(j,i))>maxx)thenmaxx=abs(A(j,i))l=jendifenddo!exchangethetwocolumnofAandFif(l/=i)thendok=1,nb=A(i,k)A(i,k)=A(l,k)A(l,k)=benddoc=F(i)F(i)=F(l)F(l)=cendif!getLsaveunderAdoj=i+1,nA(j,i)=A(j,i)/A(i,i)enddo!getUsaveupAdoj=i+1,ndok=i+1,nA(k,j)=A(k,j)-A(k,i)*A(i,j)enddoenddoenddoreturnend（2）并行程序programparaLUusempiimplicitnoneinteger,parameter::n=80real::A(n,n)real::AA(n,n),ff(n)integeri,j,m,k,icol,l,kkinteger::myid,numprocsintegerierr,rcrealmaxxreal,allocatable::B(:,:),ma(:)realt1,t2open(10,file="AAAA.txt")read(10,*)AAdoi=1,ndoj=1,nA(j,i)=AA(i,j)enddoenddocallcpu_time(t1)callMPI_INIT(ierr)callMPI_COMM_RANK(MPI_COMM_WORLD,myid,ierr)callMPI_COMM_SIZE(MPI_COMM_WORLD,numprocs,ierr)m=n/numprocsallocate(B(n,m))allocate(ma(m))if(myid==0)thencallcpu_time(t1)endifk=0doi=1,nif(mod(i-1,numprocs)==myid)thenk=k+1doj=1,nB(j,k)=A(j,i)enddoendifenddoicol=1ff=0doj=1,n-1l=jif(myid==mod(j-1,numprocs))thenmaxx=abs(B(j,icol))doi=j,nif(abs(B(i,icol))>maxx)thenmaxx=abs(B(i,icol))l=iendifenddomaxx=B(l,icol)B(l,icol)=B(j,icol)B(j,icol)=maxxdoi=j+1,nB(i,icol)=B(i,icol)/B(j,icol)ff(i)=B(i,icol)enddocallMPI_Bcast(ff,n,MPI_REAL,myid,MPI_COMM_WORLD,ierr)callMPI_Bcast(l,1,MPI_INTEGER,myid,MPI_COMM_WORLD,ierr)icol=icol+1endifcallMPI_Barrier(MPI_COMM_WORLD,ierr)if(l/=j)thendoi=1,mma(myid+1)=B(l,i)B(l,i)=B(j,i)B(j,i)