Templates for the Solution of Linear Systems Build

TemplatesfortheSolutionofLinearSystems:BuildingBlocksforIterativeMethods1RichardBarrett2MichaelBerry3,TonyF.Chan4,JamesDemmel5,JuneM.Donato6,JackDongarra3,VictorEijkhout7,RoldanPozo8,CharlesRomine9,andHenkVanderVorst10Thisistheelectronicversionofthe2ndedition,availableforsalefromSIAMsiam.org/books.LastupdatedAugust2006.1ThisworkwassupportedinpartbyDARPAandAROundercontractnumberDAAL03-91-C-0047,theNationalScienceFoundationScienceandTechnologyCenterCooperativeAgreementNo.CCR-8809615,theAppliedMathematicalSciencessubprogramoftheOfficeofEnergyResearch,U.S.DepartmentofEnergy,underContractDE-AC05-84OR21400,andtheStichtingNationaleComputerFaciliteit(NCF)byGrantCRG92.03.2FutureTechnologiesGroup,ComputerScienceandMathematicsDivision,andScientificComputingGroup,NationalCenterforComputationalScienceOakRidgeNationalLaboratory3DepartmentofComputerScience,UniversityofTennessee,Knoxville,TN37996.4AppliedMathematicsDepartment,UniversityofCalifornia,LosAngeles,CA90024-1555.5ComputerScienceDivisionandMathematicsDepartment,UniversityofCalifornia,Berkeley,CA94720.6ScienceApplicationsInternationalCorporation,OakRidge,TN378317TexasAdvancedComputingCenter,TheUniversityofTexasatAustin,Austin,TX787588NationalInstituteofStandardsandTechnology,Gaithersburg,MD9OfficeofScienceandTechnologyPolicy,ExecutiveOfficeofthePresident10DepartmentofMathematics,UtrechtUniversity,Utrecht,theNetherlands.iiHowtoUseThisBookWehavedividedthisbookintofivemainchapters.Chapter1givesthemotivationforthisbookandtheuseoftemplates.Chapter2describesstationaryandnonstationaryiterativemethods.Inthischapterwepresentbothhistoricaldevelopmentandstate-of-the-artmethodsforsolvingsomeofthemostchallengingcomputationalproblemsfacingresearchers.Chapter3focusesonpreconditioners.Manyiterativemethodsdependinpartonprecondition-erstoimproveperformanceandensurefastconvergence.Chapter4providesaglimpseofissuesrelatedtotheuseofiterativemethods.Thischapter,likethepreceding,isespeciallyrecommendedfortheexperienceduserwhowishestohavefurtherguidelinesfortailoringaspecificcodetoaparticularmachine.Itincludesinformationoncomplexsystems,stoppingcriteria,datastorageformats,andparallelism.Chapter5includesoverviewsofrelatedtopicssuchasthecloseconnectionbetweentheLanc-zosalgorithmandtheConjugateGradientalgorithm,blockiterativemethods,red/blackorderings,domaindecompositionmethods,multigrid-likemethods,androw-projectionschemes.TheAppendicescontaininformationonhowthetemplatesandBLASsoftwarecanbeobtained.Aglossaryofimportanttermsusedinthebookisalsoprovided.Thefieldofiterativemethodsforsolvingsystemsoflinearequationsisinconstantflux,withnewmethodsandapproachescontinuallybeingcreated,modified,tuned,andsomeeventuallydiscarded.Weexpectthematerialinthisbooktoundergochangesfromtimetotimeassomeofthesenewapproachesmatureandbecomethestate-of-the-art.Therefore,weplantoupdatethematerialincludedinthisbookperiodicallyforfutureeditions.Wewelcomeyourcommentsandcriticismsofthisworktohelpusinthatupda[e-mail],...,Zmatricesa,...,zvectorsα,β,...,ωscalarsATmatrixtransposeAHconjugatetranspose(Hermitian)ofAA−1matrixinverseA−TtheinverseofATai,jmatrixelementa.,jjthmatrixcolumnAi,jmatrixsubblockaivectorelementux,uxxfirst,secondderivativewithrespecttox(x,y),xTyvectordotproduct(innerproduct)x(i)jjthcomponentofvectorxintheithiterationdiag(A)diagonalofmatrixAdiag(α,β...)diagonalmatrixconstructedfromscalarsα,β...span(a,b...)spanningspaceofvectorsa,b...RsetofrealnumbersRnrealn-space||x||22-norm||x||pp-norm||x||Athe“A-norm”,definedas(Ax,x)1/2λmax(A),λmin(A)eigenvaluesofAwithmaximum(resp.minimum)modulusσmax(A),σmin(A)largestandsmallestsingularvaluesofAκ2(A)spectralconditionnumberofmatrixALlinearoperatorαcomplexconjugateofthescalarαmax{S}maximumvalueinsetSmin{S}minimumvalueinsetSPsummationO(·)“big-oh”asymptoticboundConventionsUsedinthisBookDdiagonalmatrixLlowertriangularmatrixUuppertriangularmatrixQorthogonalmatrixMpreconditionerI,In×nn×nidentitymatrixˆxtypically,theexactsolutiontoAx=bhdiscretizationmeshwidthivAcknowledgementsTheauthorsgratefullyacknowledgethevaluableassistanceofmanypeoplewhocommentedonpreliminarydraftsofthisbook.Inparticular,wethankLoyceAdams,BillCoughran,MatthewFishler,PeterForsyth,RolandFreund,GeneGolub,EricGrosse,MarkJones,DavidKincaid,SteveLee,TarekMathew,No¨elNachtigal,JimOrtega,andDavidYoungfortheirinsightfulcom-ments.WealsothankGeoffreyFoxforinitialdiscussionsontheconceptoftemplates,andKarinRemingtonfordesigningthefrontcover.ThisworkwassupportedinpartbyDARPAandAROundercontractnumberDAAL03-91-C-0047,theNationalScienceFoundationScienceandTechnologyCenterCooperativeAgreementNo.CCR-8809615,theAppliedMathematicalSciencessubprogramoftheOfficeofEnergyRe-search,U.S.DepartmentofEnergy,underContractDE-AC05-84OR21400,andtheStichtingNa-tionaleComputerFaciliteit(NCF)byGrantCRG92.03.vviContentsListofSymbolsivListofFiguresix1Introduction11.1WhyUseTemplates?.................................21.2WhatMethodsAreCovered?.............................22Itera