分裂與并行計算作業(yè)

線性代數(shù)方程組串行與并行求解方法劉爭光201311271問題考慮一般的線性方程組,最普遍的方法是先對做分解，其中為單位下三角陣，是上三角陣。于是方程組化為,率先求解這個三角形方程組，然后再求解。串行算法：（1）的分解采用部分選主元Gauss消去法進(jìn)行列消元，使得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結(jié)束（3）計算,解法類似。算法：fori=0,n-1forj=i+1,n-1endforendfor（4）流程圖開始先由，得到然后消去第一列，得到新的右端項再按照得到的方法得到即結(jié)束并行算法LU分解算法：矩陣A采用卷簾方式存儲，即把矩陣A的第i列存放在中。的算法如下：forj=0，n-2如果myid=mod(j,p),那么找到列主元素所在行選主元，找到如果把l和f廣播給其他進(jìn)程，為以后進(jìn)行行交換icol=icol+1所有進(jìn)程進(jìn)行行交換即：如果fork=icol,m-1endforendfor流程圖開始判斷要執(zhí)行語句的進(jìn)程myid=mod(j,p)選主元得到進(jìn)行行交換要用的元素l和f廣播給每個進(jìn)程所有進(jìn)程進(jìn)行行交換所有進(jìn)程求解L和U結(jié)束結(jié)果（A的LU分解）分析：由于核數(shù)為2時，通信時間占據(jù)大部分并行時間，故效率很低。A的大小核數(shù)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)