A Krylov-Schur Algorithm for Matrix Products

AKrylov-SchurAlgorithmforMatrixProducts⋆DanielKressnerInstitutf¨urMathematik,MA4-5,TUBerlin,Str.des17.Juni136,D-10623Berlin,Germany,e-mail:[e-mail]tancewillbeinsertedbytheeditorSummaryStewart’srecentlyintroducedKrylov-SchuralgorithmisamodificationoftheimplicitlyrestartedArnoldialgorithmwhichemploysreorderedSchurdecompositionstoperformrestartsandde-flationsinanumericallyreliablemanner.Thispaperdescribesavari-antoftheKrylov-Schuralgorithmsuitableforaddressingeigenvalueproblemsassociatedwithproductsoflargeandsparsematrices.ItperformsrestartsanddeflationsviareorderedperiodicSchurdecom-positionsand,bytakingtheproductstructureintoaccount,itiscapabletoachievequalitativelybetterapproximationstotheeigen-valuesofsmallmagnitude.Keywordseigenvalueproblem,matrixproduct,ArnoldimethodMathematicsSubjectClassification(1991):65F15,65F501IntroductionTheproducteigenvalueproblemconsistsofcomputingeigenvaluesandinvariantsubspacesofamatrixproductΠ=A(p)A(p−1)···A(1),(1)withthematricesA(1),...,A(p)∈Cn×n.Instancesofthisproblemarisenaturallyinavarietyofapplications,includingperiodicsys-tems[40],queueingnetworkmodels[8,37],aswellascomputational⋆SupportedbytheDFGResearchCenter“MathematicsforKeyTechnologies”(FZT86)inBerlin.2DanielKressnermethodsforanalyzingbifurcationsandcomputingFloquetmulti-pliers[26,27].Onthetheoreticalside,ithasrecentlybeendemon-stratedthattheproducteigenvalueproblemprovidesapowerfuluni-fyingconceptforaddressingstructuredeigenvalueproblemswhichinvolve,e.g.,Hamiltonian,symplectic,pseudosymmetricorunitarymatrices[42].Inprincipal,onecouldapplyanygeneral-purposeeigenvaluesolvertotheexplicitelyformedmatrixΠ.Forthesakeofnumericalstability,however,itisimportanttotakethefactthatΠisrepresentedasama-trixproductintoaccountanddevelopnumericalmethodsthatworkdirectlyonthefactorsA(1),...,A(p).TheperiodicQRalgorithm[4,18,38]issuchamethodforproductswithsmall-tomedium-sized,densefactors.RequiringO(n2p)memoryandO(n3p)computationaltime,itachievesstrongbackwardstabilityinthesensethatthecom-putedeigenvaluesandinvariantsubspacescorrespondtoamatrixproductwithslightlyperturbedfactors.Inthispaper,weproposeanalgorithmforsolvingproducteigen-valueproblemswithlarge,sparsefactors.ItisanextensionofthesocalledKrylov-Schuralgorithm[36],Stewart’smodificationoftheim-plicitlyrestartedArnoldialgorithm[24,31,32],toproducteigenvalueproblems.Todemonstratetheusefulnessofournewlydevelopedpe-riodicKrylov-Schuralgorithm,letusconsiderthefollowingsimpleexample:A(1)=A(2)=A(3)=diag(1,10−1,10−2,10−3,...,10−50).Weappliedthe(standard)Krylov-Schuralgorithmaswellasthepe-riodicKrylov-SchuralgorithmtoA(3)A(2)A(1)usingrandomstartingvectorsandthesmallestattainableconvergencetolerances.Thefol-lowingtabledisplaysthenumberofcorrectsignificantdecimaldigitsofthecomputedsevenlargesteigenvalues:EigenvalueKrylov-SchurPeriodicKrylov-Schur1151510−03141410−06101410−0981410−1241310−1511210−18011ItcanbeseenthattheaccuracyofeigenvaluescomputedbytheKrylov-Schuralgorithmdropsrapidlywithdecreasingmagnitude;theeigenvalue10−18hasnoaccuracyatall.Incomparison,theperiodicAKrylov-SchurAlgorithmforMatrixProducts3Krylov-Schuralgorithmismuchmoreaccurate;itcomputeseachdis-playedeigenvaluetoatleast11significantdigitscorrectly.Therestofthispaperisorganizedasfollows.InSection2,werecallsomebasicpropertiesoftheproducteigenvalueproblem,itsrelationtoblockcyclicmatricesandtheperiodicSchurdecomposi-tion.TheconceptsofperiodicArnoldiandKrylovdecompositionsareintroducedinSections3and4,respectively.RestartingtechniquesaredescribedinSection5,whiledeflationsarethematterofSection6.Finally,inSection7,theuseoftheperiodicKrylov-Schuralgorithmisdemonstratedfortwoapplicationareas.2TheProductEigenvalueProblemInordertodescribetheperiodicKrylov-Schuralgorithm,itisconve-nienttoreviewsomebasicfactsrelatedtotheproducteigenvalueproblem(1).Inthisrespect,thefollowingperiodicSchurdecom-positionplaysanimportantrole;justasstandardandgeneralizedSchurdecompositionsplayimportantrolesinstandardandgeneral-izedeigenvalueproblems[16].Theorem1(PeriodicSchurdecomposition[4,18])LetA(1),...,A(p)∈Cn×n,thenthereexistunitarymatricesQ(1),...,Q(p)∈Cn×nsothatT(p)=Q(1)HA(p)Q(p),T(p−1)=Q(p)HA(p−1)Q(p−1),...T(1)=Q(2)HA(1)Q(1),(2)areuppertriangularmatrices.TheperiodicSchurdecomposition(2)canbewritteninthemorecompactformT(l)=Q(l+1)HA(l)Q(l),l=1,...,p,ifweidentifythematrixQ(p+1)withQ(1).Moregenerallyspeaking,wewillmakeuseofthefollowingconvention:Throughoutthispaperweidentify⋆(l)with⋆(l−1modp)+1,where⋆canbereplacedbyanysymbol.Notethat(2)yieldsaSchurdecompositionforthematrixproductΠ:Q(1)HΠQ(1)=T(p)T(p−l)···T(1)=@.(3)4DanielKressnerHence,ift(l)iidenotestheithdiagonalelementofT(l),thentheneigenvaluesofΠaregivenbythenproductst(p)ii·t(p−1)ii···t(1)ii,withi=1,...,n.ByasuitablereorderingoftheperiodicSchurdecom-position,see[18,21],wecanlettheeigenvaluesofΠappearinanydesirableorderonthediagonalsofT(l).TheSchurdecomposition(3)alsoimpliesthatthefirstkcolumnsofQ(1)spananinvariantsubspaceofΠ.Moregenerally,itcanbeeasilyseenthatifwecons