Abstract Preconditioned Krylov subspace methods fo

PreconditionedKrylovsubspacemethodsforsolvingnonsymmetricmatricesfromCFDapplicationsqJunZhang1DepartmentofComputerScience,UniversityofKentucky,773AndersonHall,Lexington,KY40506-0046,USAReceived20July1998AbstractWeconductanexperimentalstudyonthebehaviorofseveralpreconditionediterativemethodstosolvenonsymmetricmatricesarisingfromcomputational¯uiddynamics(CFD)applications.ThepreconditionediterativemethodsconsistofKrylovsubspaceacceleratorsandapowerfulgeneralpurposemultilevelblockILU(BILUM)preconditioner.TheBILUMpreconditionerandanenhancedversionofitareslightlymodi®edversionsoftheoriginallyproposedpreconditioners.Theywillbeusedincombinationwithdi€erentKrylovsubspacemethods.Wechoosetotestthreepopulartranspose-freeKrylovsubspacemethods:BiCGSTAB,GMRESandTFQMR.Numericalexperiments,usingseveralsetsoftestmatricesarisingfromvariousrelevantCFDapplications,arereported.Ó2000ElsevierScienceS.A.Allrightsreserved.AMSclassi®cation:65F10;65F50;65N06;65N55Keywords:Multilevelpreconditioner;Krylovsubspacemethods;Nonsymmetricmatrices;CFDapplications1.IntroductionAchallengingproblemincomputational¯uiddynamics(CFD)istheecientsolutionoflargesparselinearsystemsoftheformAxˆb;…1†whereAisanonsymmetricmatrixofordern.Forexample,suchsystemsmayarisefrom®niteelementor®nitevolumediscretizationsofvariousformulationsof2Dor3DincompressibleNavier±Stokesequations.ThelargesizeoftheproblemsusuallyprecludestheconsiderationofdirectsolutionmethodsbasedonGaussianeliminationduetotheprohibitivememoryrequirement.Iterativemethodsarebelievedtobetheonlyviablesolutionmeansinsuchapplications.However,notalliterativemethodsaresuitableandef®-cientforsolvinggeneralCFDproblems.MatricesarisingfromCFDapplications,with®niteelement(volume)discretizationsonunstructureddomains,aretypicallynonsymmetricandunstructured.Thelackofregularstructurelimitsecientutili-zationofcertainrelaxationbasedfastiterativemethods,suchasthestandardmultigridmethod.Asaresult,theKrylovsubspacemethodsbecomethenaturalchoicefortheseproblems.Furthermore,manyrealisticmatricesareillconditionedandstandardKrylovsubspacemethodsappliedtosuchmatricesconvergeveryslowlyorsometimesdiverge.Theuncertaintyinperformanceofiterative(2000)825±840qThisresearchwassupportedinpartbytheUniversityofKentuckyCenterforComputationalSciences.E-mailaddress:[e-mail](J.Zhang).1URL:jzhang0045-7825/00/$-seefrontmatterÓ2000ElsevierScienceS.A.Allrightsreserved.PII:S0045-7825(99)00345-Xmethodsiscurrentlythemajorimpedanceintheacceptanceofsuchpromisingtechniquesinindustrialapplications.Fortunately,thereliabilityandrobustnessofiterativemethodscanbeimproveddramaticallybytheuseofpreconditioningtechniques.Infact,preconditioningiscriticalinmakingiterativemethodspracticallyuseful[4].Thus,inpractice,largesparsenonsymmetriclinearsystemsareoftensolvedbyKrylovsubspacemethodscoupledwithasuitablepreconditioner[17].Apreconditioningprocessconsistsofsomeauxiliaryoperations,whichsolvealinearsystemwiththematrixAapproximately.Thepreconditionercanitselfbeadirectsolverassociatedwithanearbymatrixbasedsomeincompletefactorizations,orafewiterationsofaniterativetechniqueinvolvingA,suchasthestandardrelaxationtypemethods.AlthoughexistencecanonlybeguaranteedfortherestrictedclassofM-matrices,preconditionershavebeendevelopedandaresuccessfullyusedformanyapplications.Manyef®cientpreconditionersaretailoredforthespeci®capplicationsandtheiref®cientusagesarerestrictedtotheseapplications.Althoughtheremaynotexistapreconditionerthatisef®cientforallapplications,thereisstillstronginterestindevelopingtheso-called``generalpurpose''preconditionersthatareef®cientforalargegroupofapplications.ThemultilevelblockILU(BILUM)preconditionerisoneofsuchexamples[20].ThisdomainbasedmultilevelpreconditionerusesSchurcomplementstrategiesthatarecommonindomaindecompositiontechniques.TheaimofthispaperistostudytheperformanceofseveralpromisingKrylovsubspacemethodspre-conditionedbyamodi®edBILUMinsolvingafewnonsymmetricmatricesarisingfromvariousrealisticCFDapplications.OurstudiesareempiricalandourgoalistogiveanindicationhowtheperformanceoftheKrylovsubspacemethodsisa€ectedbythequalityofthepreconditioner.Wehopetogivesomeevi-dencestosupportageneralconsensus(amongpreconditioningtechniquepractitioners)thatitisthequalityofthepreconditionersthatdeterminesthefailureorsuccessofapreconditionediterativescheme.Thusmoree€ortsshouldbeinvestedinthedesignofrobustandecientpreconditioners.Thispaperisorganizedin®vesections.Section2brie¯ydiscussestheKrylovsubspacemethods.Section3outlinestheproposedhighaccuracymultilevelblockILUpreconditioner.Section4containsournu-mericalexperimentsonseveralcollectionsofnonsymmetricmatricesfromrealisticCFDapplications.ConcludingremarksaregiveninSection5.2.KrylovsubspacemethodsThepastfewdecadeshasseena¯ourishofiterativetechniques,manyofthemaretheso-calledKrylovsubspacemethods.Theyareusuallyreferredtoasparameter-freeiterativemethods,becausetheyarefreefromchoosingparameterssuchasthoserequiredinsuccess