Preconditioning techniques for large linear system

JournalofComputationalPhysics182,418–477(2002)doi:10.1006/jcph.2002.7176PreconditioningTechniquesforLargeLinearSystems:ASurveyMicheleBenziMathematicsandComputerScienceDepartment,EmoryUniversity,Atlanta,Georgia30322E-mail:[e-mail]17,2002;revisedJuly23,2002Thisarticlesurveyspreconditioningtechniquesfortheiterativesolutionoflargelinearsystems,withafocusonalgebraicmethodssuitableforgeneralsparsema-trices.Coveredtopicsincludeprogressinincompletefactorizationmethods,sparseapproximateinverses,reorderings,parallelizationissues,andblockandmultilevelextensions.Someofthechallengesaheadarealsodiscussed.Anextensivebibliog-raphycompletesthepaper.c2002ElsevierScience(USA)KeyWords:linearsystems;sparsematrices;iterativemethods;algebraicprecondi-tioners;incompletefactorizations;sparseapproximateinverses;unstructuredgrids;multilevelmethods;parallelcomputing;orderings;blockalgorithms.1.INTRODUCTIONThesolutionoflargesparselinearsystemsoftheformAx=b,(1)whereA=[aij]isann×nmatrixandbagivenright-hand-sidevector,iscentraltomanynumericalsimulationsinscienceandengineeringandisoftenthemosttime-consumingpartofacomputation.Whilethemainsourceoflargematrixproblemsremainsthediscretization(andlinearization)ofpartialdifferentialequations(PDEs)ofellipticandparabolictype,largeandsparselinearsystemsalsoariseinapplicationsnotgovernedbyPDEs.Theseincludethedesignandcomputeranalysisofcircuits,powersystemnetworks,chemicalengineeringprocesses,economicsmodels,andqueueingsystems.Directmethods,basedonthefactorizationofthecoefficientmatrixAintoeasilyinvertiblematrices,arewidelyusedandarethesolverofchoiceinmanyindustrialcodes,especiallywherereliabilityistheprimaryconcern.Indeed,directsolversareveryrobust,andtheytendtorequireapredictableamountofresourcesintermsoftimeandstorage[121,150].Withastate-of-the-artsparsedirectsolver(see,e.g.,[5])itispossibletoefficientlysolve4180021-9991/02$35.00c2002ElsevierScience(USA)Allrightsreserved.PRECONDITIONINGTECHNIQUES419inareasonableamountoftimelinearsystemsoffairlylargesize,particularlywhentheunderlyingproblemistwodimensional.DirectsolversarealsothemethodofchoiceincertainareasnotgovernedbyPDEs,suchascircuits,powersystemnetworks,andchemicalplantmodeling.Unfortunately,directmethodsscalepoorlywithproblemsizeintermsofoperationcountsandmemoryrequirements,especiallyonproblemsarisingfromthediscretizationofPDEsinthreespacedimensions.Detailed,three-dimensionalmultiphysicssimulations(suchasthosebeingcarriedoutaspartoftheU.S.DepartmentofEnergy’sASCIprogram)leadtolinearsystemscomprisinghundredsofmillionsorevenbillionsofequationsinasmanyunknowns.Forsuchproblems,iterativemethodsaretheonlyoptionavailable.Evenwithoutconsideringsuchextremelylarge-scaleproblems,systemswithseveralmillionsofunknownsarenowroutinelyencounteredinmanyapplications,makingtheuseofiterativemethodsvirtuallymandatory.Whileiterativemethodsrequirefewerstorageandoftenrequirefeweroperationsthandirectmethods(especiallywhenanapproximatesolutionofrelativelylowaccuracyissought),theydonothavethereliabilityofdirectmethods.Insomeapplications,iterativemethodsoftenfailandpreconditioningisnecessary,thoughnotalwayssufficient,toattainconvergenceinareasonableamountoftime.Itisworthnotingthatinsomecircles,especiallyinthenuclearpowerindustryandthepetroleumindustry,iterativemethodshavealwaysbeenpopular.Indeed,theseareashavehistoricallyprovidedthestimulusformuchearlyresearchoniterativemethods,aswitnessedintheclassicmonographs[282,286,294].Incontrast,directmethodshavebeentraditionallypreferredintheareasofstructuralanalysisandsemiconductordevicemodeling,inmostpartsofcomputationalfluiddynamics(CFD),andinvirtuallyallapplicationsnotgovernedbyPDEs.However,evenintheseareasiterativemethodshavemadeconsiderablegainsinrecentyears.Tobefair,thetraditionalclassificationofsolutionmethodsasbeingeitherdirectoriterativeisanoversimplificationandisnotasatisfactorydescriptionofthepresentstateofaffairs.First,theboundariesbetweenthetwoclassesofmethodshavebecomeincreasinglyblurred,withanumberofideasandtechniquesfromtheareaofsparsedirectsolversbeingtransferred(intheformofpreconditioners)totheiterativecamp,withtheresultthatiterativemethodsarebecomingmoreandmorereliable.Second,whiledirectsolversarealmostinvariablybasedonsomeversionofGaussianelimination,thefieldofiterativemethodscomprisesabewilderingvarietyoftechniques,rangingfromtrulyiterativemethods,liketheclassicalJacobi,Gauss–Seidel,andSORiterations,toKrylovsubspacemethods,whichtheoreticallyconvergeinafinitenumberofstepsinexactarithmetic,tomultilevelmethods.Tolumpallthesetechniquesunderasingleheadingissomewhatmisleading,especiallywhenpreconditionersareaddedtothepicture.ThefocusofthissurveyisonpreconditioningtechniquesforimprovingtheperformanceandreliabilityofKrylovsubspacemethods.Itiswidelyrecognizedthatpreconditioningisthemostcriticalingredientinthedevelopmentofefficientsolversforchallengingproblemsinscientificcomputation,andthattheimportanceofpreconditioningisdestinedtoincreaseevenfurther.Thefollowingexcerptfromthetextbook[272,p.319]byTref