Consistency of Krylov-W-methods in initial value p

ConsistencyofKrylov-W-methodsininitialvalueproblemsR.WeinerandB.A.SchmittAbstractWeconsiderW-methodsandROW-methodsforstiinitialvalueproblems,wherethestageequationsaresolvedbyKrylovtechniques.Byusingacertain‘multipleArnoldiprocess’overallstagestheorderofthefully-implicitone-stepschemeispreservedwithsmallKrylovdimensions.BoundsforthesedimensionsdependingonlyontheactualW-method,notonthedimensionoftheODE,arederived.Severalexamplemethodsandpossibleextensionstootherlinearly-implicitmethodsarediscussedandconsequencesforstepsizeselectionstrategiesarepointedout.Keywords.W-methods,Krylovsubspaces,multipleArnoldiprocessAMS(MOS)subjectclassications.65L06,65F10Shorttitle:Consistencyinvestigations1IntroductionForthenumericalsolutionofstiinitialvalueproblemsy0(t)=f(t;y(t))y(t0)=y02Rn;(1.1)implicitorlinearlyimplicitmethodshavetobeusedduetostabilityrequirements.Rosen-brock-typeschemeslikeROW-methods(e.g.[9])haveshowntobeveryecientsolutionmethodsforsuchproblems.Theirclassicalformulationisforautonomousproblemsonly.Thenonautonomousformofas-stageROW-methodisgivenby[7],[16](IhA)(ki+i1Xj=1ijkj)=fi+i1Xj=1ijkj+hdift(1.2)fi=f(tm+cih;u(i)m+1)u(i)m+1=um+hi1Xj=1aijkjum+1=um+hsXi=1bikiThisworkwassupportedbyDeutscheForschungsgemeinschaft1whereft=ft(tm;um);di=+i1Xj=1ij;ci=i1Xj=1aij;andA=fy(tm;um):(1.3)ThisversionhasthesameorderfornonautonomousproblemsastheclassicalROW-methodforautonomousones.Thescheme(1.2)isaW-method([14])ifthepartialderivativeftisnotusedfornonau-tonomousproblems.Inthiscase,thematrixAneednotbegivenby(1.3),anarbitrarymatrixmaybeusedinstead.Thischoice,however,leadstoanincreaseinthenumberoforderconditionsfortheW-method.InconnectionwithKrylovtechniqueswewillconsiderW-methodswhichdouseAgivenby(1.3).So,forautonomousproblemstheyareidenticaltoROW-methods.Butfornonautonomousproblemstheirorderislower,ingeneral,thanthatofthecorrespondingROW-method.WithrespecttoB-consistencyW-methodscanhavefavourableproperties[17].Tobothtypesofmethodsusing(1.3)wewillreferinthesequelasthe\underlyingRosenbrock-typemethod.Forlargedimensionnthesemethods(likeanyimplicitmethod)spendmostoftheircomputingtimefortheevaluationoftheJacobianandforthesolutionofthelinearstageequations.ByusingastandarditerationmethodlikeGMRESorArnoldi’smethodforsolvingeachindividualstageequationthiseortmaybereduced.However,suchasimplecombinationmaywasteeortbyneglectingdependenciesamongthedierentsystems.TheKrylov-W-methodsconsideredherere-useinformationfromtheArnoldiprocessinearlierstagesbyreplacingthematrixA=fy(tm;um)in(1.2)byalow-rankapproximationTi=QiQTiA;(1.4)atstagei,wheretheorthogonalmatrixQi=fq1;:::;q{ig2Rn;{iiscomputedbyamultipleArnoldiprocessdescribedinsection3.TheimportantpointhereisthatQi(i1)isanextensionofQi1.Thestageequation(1.2)thenbecomes(IhTi)(ki+i1Xj=1ijkj)=fi+i1Xj=1ijkj+hdift=:wi:(1.5)Since(IhQiQTiA)1=I+hQi(IhHi)1QTiA;Hi=QTiAQi2R{i;{i;(1.6)thestageincrementkimaybecomputedbyki=(IhTi)1wii1Xj=1ijkj=[I+hQi(IhHi)1QTiA]wii1Xj=1ijkj;(1.7)2andwehavetosolveequationsofdimension{ionly.If,furthermore,theright-handsidewiatthei-thstagebelongstothesubspaceKi=spanfq1;:::;q{ig=rangeQi;(1.8)i.e.,QiQTiwi=wi;(1.9)therelation(1.7)simpliesfurther,leadingtothefollowingnalformoftheKrylov-W-methodki=Qi(IhHi)1QTiwii1Xj=1ijkj(1.10)wi=fi+i1Xj=1ijkj+hdift;fi=f(tm+cih;u(i)m+1)u(i)m+1=um+hi1Xj=1aijkj;um+1=um+hsXi=1biki:Condition(1.9)willbesatisedbythemultipleArnoldiprocessdescribedinsection3.SincethecomputationaleortofArnoldi’smethodincreaseswith{2n,theKrylov-W-methodcanbeecientforfairlylowdimensions{ionly.Ontheotherhand,ecientstepsizeselectionstrategiesrequirecertainminimumdimensionsinordertohavethemainpropertiesoftheoverallscheme,namelyaccuracyofthenumericalsolution,andstabilityofthenumericalscheme.StabilityresultsforKrylov-W-methodsusingtheclassicalArnoldiprocess(withonestartonly)aregivenin[3],andforthemultipleArnoldiprocessin[12].Numericalcomparisonsofa3-stageW-methodusingamultipleArnoldiprocessinSchmittandWeiner[13]withthecodeVODPKofByrne,BrownandHindmarsh[4]forsemidiscretizedtwo-dimensionalparabolicequationsshowedagoodperformanceofthisKrylov-W-methodandconrmedgoodstabilityproperties.Inthispaperwewillconcentrateontherstitem.WepresentastrategyforthemodiedmultipleArnoldiprocessthatguaranteestheKrylov-W-methodtohavethesameorderastheunderlyingRosenbrock-typemethodandgiveupperboundsforKrylovdimensionsthataresucientforthisproperty.Themainresultis,thattherequireddimensions{idonotdependonthedimensionnof(1.1).Insection2wedescribethemultipleArnoldiprocessforthecomputationofthematricesQiandHiusedintheKrylov-W-method(1.10)andprovesomebasicproperties.Insection3wederiveestimatesfortheconsistencyorderofmethod(1.10).TheserelyheavilyoncertainfeaturesofthemultipleArnoldiprocess.ForanunderlyingRosenbrock-typemethodoforderpwegiveastrategythatensuresorderpfor(1.10),aswell.3Section4givesexamplesofmethods,forbothversionsusingftornot.Insection5wenallypresentanoutlinehowtheseresultscanbeadaptedtootherlinearly-implicitmethods,e.g.adaptiveRu