求解大型矩阵特征值问题的并行精化Davidson方法

265200910CHINESEJOURNALOFENGINEERINGMATHEMATICSVol.26No.5Oct.2009:1005-3085(2009)05-0922-07Davidson1;2,1(1-210016;2-222005):DavidsonIBM-P650:Davidson:AMS(2000)65F15;65Y05:O241;O246:A1LanczosArnoldiDavidsonJacobi-Davidson[1;2]LanczosDavidsonUnder-woodLanczos[3]Lanczos[4]CrouzeixDavidson[5;6]Ax=¸x(1)Ritz~xiRitz~¸ik(A¡~¸iI)^xik2=minx2Vi;kxk2=1k(A¡~¸iI)xk2(2)^xiRitz~xi[7-12]k(A¡~¸iI)^xik2=¾min(AVi¡~¸iVi);(3)^xi=Vi^zi;^zi(A¡~¸iI)Vi¾mink^zik2=1VTi(A¡~¸iI)H(A¡~¸iI)Vi^zi=¾2min^zi;(4)^xi=Vi^ziRitzk(A¡~¸iI)^xik2¾min^¸i=^xHiA^xi:2007-11-13.:(196211)..5Davidson923BalleCullumNoolVanderPloegLanczosJacobi-Davidson[13;14]DavidsonDavidsonIBM-P6502DavidsonAnDavidsonGalerkin-RitzRitzRitzV[1]DavidsonDavidson1(Davidson[5])1)mlV1=[v1;v2;¢¢¢;vl]2)k=1;2;¢¢¢3)Wk=AVk4)Hk=VTkWk5)Hkl()(~¸k;i;yk;i);i=1;¢¢¢;l6)Ritz~xk;i=Vkyk;i;i=1;¢¢¢;l7)rk;i=(~¸k;iI¡A)~xk;i;i=1;¢¢¢;l8)krk;ik2;i=1;¢¢¢;l9)9)Ck;itk;i=rk;i;i=1;¢¢¢;l10)dim(Vk)+l6mVk+1=MGS(Vk;tk;1;tk;2;¢¢¢;tk;l)3)11)11)V1=MGS(~xk;1;¢¢¢;~xk;l;tk;1;tk;2;¢¢¢;tk;l)2)1MGSGram-SchmidtGram-SchmidtVk=(v1;¢¢¢;vs)vj=tk;j¡s;j=s+1;¢¢¢;s+l1Vk+1=MGS(Vk;tk;1;tk;2;¢¢¢;tk;l)fori=1toldoforj=s+1tos+ldovj=vj¡(vj;vi)viendforendforfori=s+1tos+ldovi=vi=kvik2forj=i+1tos+ldovj=vj¡(vj;vi)viendforendforkCk;i~¸k;iI¡ACk;i~¸k;iI¡ACk;itk;i=rk;i(i=1;¢¢¢;l)tk;i~xk;i(i=1;¢¢¢;l)tk;i(i=1;¢¢¢;l)Olsen[15]Ck;itk;i=rk;i+i~xk;i;tk;i?~xk;i;i=1;¢¢¢;l;(5)92426tTk;i~xk;i=0i=¡~xTk;iC¡1k;irk;i=~xTk;iC¡1k;i~xk;i;i=1;¢¢¢;l;(6)MGSDavidson~¸k;iVTi(A¡~¸k;iI)T(A¡~¸k;iI)Vi=WTkWk¡2~¸k;iHk+~¸2k;iI;Sk;i=WTkWk¡2~¸k;iHk+~¸2k;iI;i=1;¢¢¢;l;(7)Davidson22(Davidson)1)mlV1=[v1;v2;¢¢¢;vl]2)k=1;2;¢¢¢;3)Wk=AVk4)Hk=VTkWk5)Hkl()(~¸k;i;yk;i);i=1;¢¢¢;l6)Ritz~xk;i=Vkyk;i;i=1;¢¢¢;l7)rk;i=(~¸k;iI¡A)~xk;i;i=1;¢¢¢;l8)krk;ik2;i=1;¢¢¢;l9)9)dim(Vk)+l6mCk;itk;i=rk;i;i=1;¢¢¢;lVk+1=MGS(Vk;tk;1;¢¢¢;tk;l)3)10)dim(Vk)+lmSk;i=WTkWk¡2~¸k;iHk+~¸2k;iI;i=1;¢¢¢;l(¾21;i;^zi);i=1;¢¢¢;l11)^xk;i=Vk^zi;i=1;¢¢¢;l12)V1=[^xk;1;¢¢¢;^xk;l]2)3Davidson3.1DavidsonnAAnpPiAiAimimiAi1Ai1+m1¡12Davidson3(Davidson)1)mlV1=[v1;v2;¢¢¢;vl]2)k=1;2;¢¢¢3)PiWk;i=AiVk4)PiHk;i=VTk;iWk;i5)PiHk=Ppj=1Hk;j6)PiHkl()(~¸k;j;yk;j);j=1;¢¢¢;l7)Ritz~xk;j=Vkyk;j;j=1;¢¢¢;l8)rk;j=(~¸k;jI¡A)~xk;j;j=1;¢¢¢;l9)krk;jk2;j=1;¢¢¢;l10)10)dim(Vk)+l6mCk;jtk;j=rk;j;j=1;¢¢¢;lVk+1=MGS(Vk;tk;1;¢¢¢;tk;l)3)5Davidson92511)dim(Vk)+lmPiWTk;iWk;iWTkWkSk;j=WTkWk¡2~¸k;jHk+~¸2k;jI;j=1;¢¢¢;l;Sk;j(j=1;¢¢¢;l)(¾21;j;^zj);j=1;¢¢¢;l12)^xk;j=Vk^zj;j=1;¢¢¢;l13)V1=[^xk;1;¢¢¢;^xk;l]2)3.236)Hk11)Wk=AVkHk=VTkWkPiWk;i=AiVkPiWkmiVTk=(VTk;1;¢¢¢;VTk;p)TAVTkWkPiHk;i=VTk;iWk;iHk=pXj=1Hk;j;()HkHkl~¸k;j(j=1;¢¢¢;l)WTkWkPiWTk;iWk;iSk;j=WTkWk¡2~¸k;jHk+~¸2k;jI;j=1;¢¢¢;l;Sk;j(¾21;j;^zj);j=1;¢¢¢;lRitz~xk;j(j=1;¢¢¢;l)Yk=(yk;1;¢¢¢;yk;l);Xk=(~xk;1;¢¢¢;~xk;l);XkAXk=(XTk;1;¢¢¢;XTk;p)TXk;i=Vk;iYk;i=1;¢¢¢;p;PiXk;i^xk;j;j=1;¢¢¢;lrk;j=~¸k;j~xk;j¡Wkyk;j(j=1;¢¢¢;l)Rk=(rk;1;¢¢¢;rk;l)XkRkRk=(RTk;1;¢¢¢;RTk;p)TRk=Xkdiag(~¸k;1;¢¢¢;~¸k;l)¡WkYk;Rk;i=Xk;idiag(~¸k;1;¢¢¢;~¸k;l)¡Wk;iYkRk;iCk;jtk;j=rk;j(j=1;¢¢¢;l)Ck;j=(~¸k;jI¡MA)MAAMA=DAPitk;j(tk;j)s=(rk;j)s=(~¸k;j¡as;s);s=i1;¢¢¢;i1+mi¡1;j=1;¢¢¢;l;Tk=(tk;1;¢¢¢;tk;l)PiTkmiVk+13.3926263Vk+1PiVk+1miVk+1Gram-Schmidt(CGS)MGSCMGSCMGSCGSMGSm¡dim(Vk)lCGStk;j(j=1;¢¢¢;l)tk;j(j=1;¢¢¢;l)MGS4ptpp()Sp=t1=tp´()=10¡6IBM-P650MPIPII30064MIBM-P65081.45GHzPower4CPU16GBFastTIBM-P650FortranMPI1nA=(aij)i=jaij=iji¡jj6wi6=jaij=¢ji¡jjaij=0wAn=7000w=262¢=0:75[16]DavidsonDavidsonA51-31:15k¸k1¡4:0931326£10¡220.580471031.016409741.728426252.28016482:1DavidsonDavidsonptSp´ptSp´122.4511001304.131100214.481.5577.52187.11.63813:IBM-P6501DavidsonDavidsonptSp´ptSp´16.2811001103.38110023.881.6281260.461.7185.542.332.767.4437.322.7769.381.434.3954.9822.194.6658.25Davidson9272DavidsonDavidson110[17]KM¸Kx=¸Mxf=p¸=2¼By=~¸yB=L¡1ML¡TK=LLT~¸=1=¸tk;i=C¡1k;irk;iC¡1k;i(~¸k;i¡B)¡1C¡1k;i=1~¸k;i³I+1~¸k;iB´:IBM-P65041:4:IBM-P6502DavidsonDavidsonptSp´ptSp´18.27110017.63110024.481.8592.324.081.8793.542.533.2781.742.303.3282.981.585.2365.481.435.3466.71101625Sk;j(j=1;¢¢¢;l)(¾21;j;^zj)(j=1;¢¢¢;l)92826[1]DavidsonER.Theiterativecalculationofafewlowesteigenvaluesandcorrespondingeigenvectorsoflargereal-symmetricmatrices[J].JournalofComputationalPhysics,1975,17(1):87-94[2]SleijpenGLG,VanderVorstHA.AJacobi-Davidsoniterationmethodforlineareigenvalueproblem[J].SIAMJMatrixAnalAppl,1996,17(2):401-425[3]UnderwoodR.AnIterativeBlockLanczosMethodfortheSolutionofLargeSparseSymmetricEigenprob-lems[D].Stanford:StanfordUniversity,1975[4]DaiH,LancasterP.PreconditionedblockLanczosalgorithmforsolvingsymmetriceigenvalueproblems[J].JournalofComputationalMathematics,2000,18:365-374[5]CrouzeixM,PhilippeB,SadkaneM.TheDavidsonmethod[J].SIAMJSciComput,1994,15(1):62-76[6]SadkaneM,SidjeRB.ImplementationofavariableblockDavidsonmethodwithde°ationforsolvinglargesparseeigenproblems[J].NumericalAlgorithms,1999,20:217-240[7]JiaZX.Re¯nediterativealgorithmbasedonArnoldi'sprocesssforlargeunsymmetriceigenproblems[J].LinearAlgebraanditsApplications,1997,259:1-23[8]JiaZX.Are¯nedsubspaceiterationalgorithmforlargesparseeigenproblems[J].AppliedNumericalMath-ematics,2000,32(1):35-52[9]JiaZX.AnanalysisoftheRayleigh-Ritzmethodforapproximati