TOEPLITZ PRECONDITIONING OF TOEPLITZ MATRICES ― AN

TeknillisenkorkeakoulunmatematiikanlaitoksentutkimusraporttisarjaEspoo1999A404TOEPLITZPRECONDITIONINGOFTOEPLITZMATRICES—ANOPERATORTHEORETICAPPROACHJarmoMalinenTEKNILLINENKORKEAKOULUTEKNISKAHÖGSKOLANHELSINKIUNIVERSITYOFTECHNOLOGYTECHNISCHEUNIVERSITÄTHELSINKIUNIVERSITEDETECHNOLOGIED’HELSINKI(insideofthefrontcover,nottobeprinted)TeknillisenkorkeakoulunmatematiikanlaitoksentutkimusraporttisarjaEspoo1999A404TOEPLITZPRECONDITIONINGOFTOEPLITZMATRICES—ANOPERATORTHEORETICAPPROACHJarmoMalinenHelsinkiUniversityofTechnologyDepartmentofEngineeringPhysicsandMathematicsInstituteofMathematicsJarmoMalinen:ToeplitzPreconditioningofToeplitzMatricesanOperatorTheoreticApproach;HelsinkiUniversityofTechnologyInstituteofMathematicsResearchReportsA404(1999).Abstract:WestudythepreconditioningofToeplitzmatricesTn[f]bysomeotherToeplitzmatrices.Wedividethepreconditionedmatrixintotwoparts.Oneofthesepartshasasingularvaluedecaythatdependsonthesmoothnessofthesymbolf.Theremainingpartisregardedaspreconditioningerror,andithasthestructureofToeplitzmatrix.Weindicatethatthepreconditionerscanbegeneratedbyamultitudeofapproximationtheoreticmethodsapplieduponthesymbolofsuchsystem.Moreover,theToeplitzpreconditioningerrorcanbemadearbitrarilysmallifthedegreeofpreconditioningisincreased.OurresultsshowthattheKrylovsubspacemethods(suchasGMRESorCG)willperforminitiallyatsuperlinearspeedwhenapplieduponsuchprecondi-tionedsystem.TheconnectionbetweensmoothnessofthesymbolfandthenumericalpropertiesofmatricesTn[f]withincreasingnispresented.AMSsubjectclassications:65T10,65T20,47B35.Keywords:Toeplitzoperator,Krylovsubspacemethods,preconditioning,speedestimate,superlinear,linear.ISBN951-22-4354-7ISSN0784-3143Edita,Espoo,1999HelsinkiUniversityofTechnologyDepartmentofEngineeringPhysicsandMathematicsInstituteofMathematicsP.O.Box1100,02015HUT,Finlandemail:[e-mail]:/author’semail:31IntroductionAstandardlineofattackinthesolutionoflinearsystemsisthefollowing:First,thebiglinesoftheproblemareinvestigated,sothataroughapprox-imationoftheinverseoperator,calledpreconditioner,canbefound.Theapplicationofapreconditionereliminatesthelargeamountofdisorderintheproblem.Asuccessfullypreconditionedlinearoperatoris,insomeap-propriatesense,almostanidentityoperator.Theremainingdisorderiseliminatedbyvariousiterativeprocedures(Krylovsubspacemethods,suchasCGofGMRES),possiblyusingparallelcomputationtechniques.Inthispaper,weapplytheseideastoaspecialclassofmatrices,namelyToeplitzma-trices.ItseemsthatToeplitzmatricesappearpracticallythroughoutalltheappliedmathematics.Forexample,theyareusedinthenumericalsolutionofconvolutiontypeequationswhentheyapproximateaninnitedimensionalobject(e.g.Toeplitzoperator),see[6].Letusconsidersomerequirementsthatagoodpreconditionershouldhave.Inpractice,thepreconditioningcanbedoneeitherbeforeorafterthediscretizationoftheproblem.Intherstway,thepreconditioningisdonetotheoriginal(innitedimensional)operatorabstractlyonapieceofpaper,andtheiteratorsoftwareworkswith(anitedimensionaldiscretizationof)thepreconditionedoperator.Fortheparallelimplementationoftheiteratortobeeective,thepreconditionedoperatorshould,insomesense,beeasilydecomposableintosmallerblocksthatdonotcommunicatetoomuchwitheachother;thereaderisinstructedtothinkofthestructuresthatresemblethedecompositionofacompactoperatorintoitsgeneralizedeigenspaces.Itisalsoclearthattheiterationoftheblocksshouldconvergefastforagoodpreconditioner.Thesecondwaytopreconditionisthefollowing:Theinnitedimensionalproblemisdiscretizedrst,andthenthenitedimensionalmatrixofthedis-cretizedproblemispreconditioned.Nowthepreconditionedmatrixwouldnotnecessarilyexistsinthememoryofthecomputer,becausethiswouldrequireanumericalcomputationofamatrix-matrixproduct.Instead,thepreconditionerisappliedinsideeachiterationloopoverandoveragain,sothatonlymatrix-vectorproductsarecalculatedbythecomputersoftware.Itisnowdesirablethatthepreconditioner-vectorproductisnumericallycon-venient.In1986,G.Strang[14]proposedthatacirculantToeplitzprecondi-tionercouldbeappliedonToeplitzmatrices.Aniterativeconjugategradientmethod(CG)isthenusedtocompletetheinversion.SeveralotherclassesofToeplitzpreconditionershavebeenstudiedbymanyauthors;bandToeplitzpreconditionersforsystemswithpositivesymbols[1],circulantToeplitzpre-conditionersassociatedtoconvolutionkernels[3],circulantToeplitzprecon-ditionerswithcomplexsymbols[4],preconditionersarisingfrominversesym-bol[2],tomentionfew.Thecommonfoundationforalltheseapproachesisthepossibilityofcal-culatingtheToeplitz-vectorproductinnlogntimebyFFT,wherenisthe4dimensionofthematrix(regardedasthelevelofdiscretizationiftheoriginalproblemisinnitedimensional).Itfollowsthatthecalculationofasingleit-erationstepforaToeplitzsystemisfast,buttheconvergenceoftheiterationispoor,withoutproperpreconditioning.Becauseofthementionednlogncomplexityproperty,itseemsacomputationallyattractivealternativetouseaToeplitzmatrixasapreconditionertoaToeplitzsystem.Ofcourse,iftheiterationofthepreconditionedsystemw