On the solution of non-symmetric linear systems by

InstituteforNumericalandComputationalAnalysisDublin,IrelandOntheSolutionofNon-SymmetricLinearSystemsbythePreconditionedConjugateGradientSquaredMethodGuGuidingPreprintNo.7(1987)September1987ONTHESOLUTIONOFNON-SYMMETRICLINEARSYS-TEMSBYTHEPRECONDITIONEDCONJUGATEGRADI-ENTSQUAREDMETHODGUGUIDINGNumericalAnalysisGroup,TrinityCollege,Dublin2,IrelandAbstract:WhentheConjugateGradientSquared(CGS)methodisusedtosolvealinearsystem,anefficientpreconditioningmethodisexpectedtoaccelerateitsspeed.TherelaxedincompleteLU-factorisation(RILU)[9]issuchapreconditioner.ThisreportpresentstheconditionsfortheexistenceoftheRILU,andanalysestheconditionin[8]forthestabilityofthecomputationsinvolvingthetriangularfactorsinthepreconditioningoperationintheiterativeprocessofthepreconditionedCGS.Achoiceofrelaxationparameter!undertheseconditionsisobtainedbynumericalexperiments.Ouranalysisisforaclassofspeciallinearsystems,inwhichthecoefficientmatrixisapentadiagonalmatrixwithconstantentriesoneachdiagonal.1.IntroductionDiscretisationbythefiniteelementmethodorthefinitedifferencemethodofalinearnon-selfadjointpartialdifferentialequationgivesasystemoflinearequationsAx=b(1:1)whereAisalarge,unsymmetric,sparserealmatrixofordernn;bisan-dimensionalvectorandxisanunknownn-dimensionalvector.Itisimportanttoknowhowtofindthesolutionxof(1.1)aseasilyaspossiblesincenisaverylargenumber.TheConjugateGra-dientSquared(CGS)method[7],aniterativemethod,isanefficientwaywhenusedinacombinationwithapreconditioningtechnique.Weknowthat,iftheCGSmethodisusedtosolve(1.1),thesmallertheconditionnumber(A)is,themorequicklyxisobtained.ThepreconditioningtechniquetreatsinsteadapreconditionedsystemC1Ax=C1b(1:2)whereC,calledapreconditioningmatrix,isanapproximationtoA.IfwechoosesomeCtomake(C1A)smallerthan(A),the2solutionxcanbeobtainedmorequicklybysolving(1.2)ratherthan(1.1).TheproblemishowtochooseabetterCtomakeasmaller(C1A).IncompleteLU-factorisation(ILU(k))[2],[5]andmod-ifiedincompleteLU-factorisation(MILU(k))[3]aretwoefficientpreconditioningmethods.Afterbothmethods,Axelsson[9]pre-sentedtherelaxedincompleteLU-factorisation(RILU(!;k))whichcontainsaparameter!(0!1).For!=0themethodreducestotheILU(k)whilefor!=1themethodreducestotheMILU(k).Moreover,itissaidin[3]thattheMILU(k)ismoreefficient,i.e.xcanbeobtainedmorequickly,thantheILU(k)forawideclassproblems.Itisalsoconcludedin[9]thattherelaxedmethodperformslightlybetterthantheunrelaxedonebutthe‘optimal’valueof!,whichisobtainedbynumericalexperiment,isalwayscloseto1.Inaddition,thelargerkisused(see[5])(aboutk,seethenoteonpage3),thefewertheiterativenumberofaniterativemethodcombinedwithRILU(!;k)becomes,whichisonlyanaturalideabutthereisnoproofin[5].However,theseconclusionsshouldbeundersomeconditions(seeSection4).WeusetheCGScombinedwiththepreconditioningtechniquetosolve(1.2),andapreconditioningmatrixCisobtainedfromRILU(!;k).Sotheexistence,thestabilityofRILUandthestabil-ity(see[8])ofthecomputationsinvolvingthetriangularfactorsinthepreconditioningoperationofthepreconditionedCGSshouldbediscussed.Otherwise,theefficiencyofthepreconditioningmethodcannotbeguaranteed(seeSection4).Theconditionsfortheexis-tenceofRILU(!;k)andforthestabilityofthecomputationsinvolv-ingthetriangularfactorsaredependentonagivenmatrix.Inotherwords,theconditionhasrelationto!,e.g.for!=0,i.e.ILU(k),theexistenceisprovenifAisaM-matrixin[2](ArealmatrixA=faijgwithaij0(i6=j)isaM-matrixifAisnon-singular,andA10.see[1]),andfor!=1,i.e.MILU(k),theexistenceisprovenifAisadiagonaldominance~M-matrixin[6](ArealmatrixA=faijgwithaij0(i6=j)isa~M-matrixifaii0;andaij06=0,atleastforonej0i,see[6]),butitsexistencecannotbeguaranteedifAonlyisaM-matrix(seeRemark2.1).SoforageneralcoefficientmatrixA,suchasadiagonallynon-dominantmatrixorannotM-matrix,weshouldchooseasuitable!andkto3obtainanefficientpreconditioningmatrixCfromRILU(!;k).Inthiscase,isthereasuitableparameter!suchthatamoreefficientpreconditioningmatrixCcanbeobtainedfromRILU(!;k)thanformedfromRILU(0,k)?andwhataretheconditionsforexistenceandstabilitywhenchoosingsucha!andk?Foraclassofpentadiagonalmatriceswithconstantentriesoneachdiagonal,thisreportpresentstheconditionsforexistenceofRILU(!;k)inSection2.Th2.1andTh2.5givetheexistenceofRILU(!;k)fork=0andk=1.Inthesenseof‘diagonaldom-inance’*,forfixedk,thelargerthevalueof!is,thestrongertheconditionis,andforfixed!,theconditionfork=1isstrongerthanonefork=0bynumericalcomparison.Th2.3guaranteesastableprocessofRILU(!;k)fork=0.InSection3,wediscussestheconditionin[8]forstabilityofthecomputationsinvolvingthetrian-gularfactorsinthepreconditioningoperationintheiterativeprocessofthepreconditionedCGS.InSection4,wechoosesomecoefficientmatricestomakeacomparisonamongthepreconditioningmatricesformedfromRILU(!;k)withdifferent!andkbyshowingtheiter-ativenumberofCGScombinedwiththepreconditioningtechnique.Undertheseconditionsabove,achoiceofrelaxationparameter!isobtainedinRILU(!;0)bynumericalexperiment.AndalsowefindthatthereisagreateffectonconvergencerateofCGSwhentheconditionforexistenceofRILUdegeneratesandsomeeffectifthestabilitycondition.2.