Iterative Solution of Linear Systems in the 20-th

IterativeSolutionofLinearSystemsinthe20-thCenturyYousefSaadHenkA.vanderVorstyAbstractThispapersketchesthemainresearchdevelopmentsintheareaofiterativemethodsforsolvinglinearsystemsduringthe20thcentury.Althoughiterativemethodsforsolvinglinearsystemsndtheiroriginintheearlynineteenthcentury(workbyGauss),theeldhasseenanexplosionofactivityspurredbydemandduetoextraordinarytechnologicaladvancesinengineeringandsciences.Thepastvedecadeshavebeenparticularlyrichinnewdevelopments,endingwiththeavailabilityoflargetoolboxofspecializedalgorithmsforsolvingtheverylargeproblemswhichariseinscienticandindustrialcomputationalmodels.Asinanyotherscienticarea,researchiniterativemethodshasbeenajourneycharacterizedbyachainofcontributionsbuildingoneachother.Itistheaimofthispapernotonlytosketchthemostsignicantofthesecontributionsduringthepastcentury,butalsotorelatethemtooneanother.1IntroductionNumericallinearalgebraisanexcitingeldofresearchandmuchofthisresearchhasbeentriggeredbyaproblemthatcanbeposedsimplyas:GivenA2Cmn,b2Cm,ndsolutionvector(s)x2CnsuchthatAx=b.Manyscienticproblemsleadtotherequirementtosolvelinearsystemsofequationsaspartofthecomputations.Fromapuremathematicalpointofview,thisproblemcanbeconsideredasbeingsolvedinthesensethatweexplicitlyknowitssolutionintermsofdeterminants.Theactualcomputationofthesolution(s)mayhoweverleadtoseverecomplications,whencarriedoutinniteprecisionandwheneachbasicarithmeticoperationtakesnitetime.Eventhe\simplecasewhenn=mandAisnonsingular,whichisatrivialproblemfromamathematicalpointofview,maybecomeverycomplicated,fromacomputationalpointofview,andmayeventurnouttobeimpossible.ThetraditionalwaytosolveanonsingularlinearsystemistoemployGaussianelimination,and,withallitsenhancements,toovercomenumericalinstabilities.ThisprocesscanbecarriedoutinO(n3)basicoatingpointoperations(additionsandmultiplications,assumingn=m).Manyapplicationsleadtolinearsystemswithalargen(wherethenotionof\largedepends,ofcourse,onthecapacityoftheavailablecomputer),anditbecamesoonevidentthatonehastoexploitspecicpropertiesoftheAathandinordertomakesolutionofthesystemfeasible.ThishasledtovariantsofGaussianeliminationinwhichthenon-zerostructureofAisexploited,sothatmultiplicationswithzeroresultareavoidedandthatsavingsincomputerstoragecouldberealized.Anotherdirectionofapproachwasbasedonthesolutionofanearbylinearsystem,withamatrixthatadmitsacomputationallyinexpensiveprocess(intermsofcomputingtimeandcomputerstorage),andtoembedthisinaniterativeprocess.Bothapproachesaimatmakingtheimpossiblepossible,andforthenoviceinthiseldthismayseemtobejustacollectionofcleverprogrammingtricks:\inprinciplesolvingtheproblemiswell-understoodbutonehastobewell-organizedtomakethecomputationalprocessalittlefaster.Forthisnoviceitwillcertainlycomeasabigsurprisethatawhole,stillincomplete,mathematicalframeworkhadtobedevelopedwithdeepandelegantresults.Asaresult,relevantsystemscouldbesolvedmanyordersofmagnitudefaster(andalsooftenmoreaccurate)thanbyastraightforwardGaussianDepartmentofComputerScienceandEngineering,UniversityofMinnesota,Minneapolis,USA,[e-mail]/CCRandbytheMinnesotaSupercomputerInstitute.yDepartmentofMathematics,UtrechtUniversity,Utrecht,TheNetherlands,[e-mail],wewillsketchthedevelopmentsandprogressthathastakenplaceinthetwentiethcenturywithrespecttoiterativemethodsalone.Aswillbeclear,thissubeldcouldnotevolveinisolation,andthedistinctionbetweeniterativemethodsandGaussianeliminationmethodsissometimesarticial-andoverlapbetweenthetwomethodologiesissignicantinmanyinstances.Nevertheless,eachofthetwohasitsowndynamicsanditmaybeofinteresttofollowoneofthemmoreclosely.Itislikelythatfutureresearchersinnumericalmethodswillregardthedecadejustpassedasthebeginningofanerainwhichiterativemethodsforsolvinglargelinearsystemsofequationsstartedgainingconsiderableacceptanceinreal-lifeindustrialapplications.Inlookingatpastliterature,itisinterestingtoobservethatiterativeanddirectmethodshaveoftenbeenincompetitionforsolvinglargesystemsthatariseinapplications.Aparticulardiscoverywillpromoteagivenmethodfromonecamponlytoseeanotherdiscoverypromoteacompetingmethodfromtheothercamp.Forexample,the50sand60ssawanenormousinterestinrelaxation-typemethods-promptedbythestudiesonoptimalrelaxationandtheworkbyYoung,Varga,Southwell,Frankelandothers.Alittlelater,sparsedirectmethodsappearedthatwereverycompetitive-bothfromthepointofviewofrobustnessandcomputationalcost.Tothisday,therearestillapplicationsdominatedbydirectsolversandothersdominatedbyiterativesolvers.Becauseofthehighmemoryrequirementofdirectsolvers,itwassometimesthoughtthatthesewouldeventuallybereplacedbyiterativesolvers,inallapplications.However,thesuperiorrobustnessofdirectsolverspreventedthis.Ascomputershavebecomefaster,verylargeproblemsareroutinelysolvedbymethodsfrombothcamps.Iterativemethodswere,evenhalfwayinthetwentiethcentury,notalwaysviewedaspromising.Forinstance,Bodewig[22,p.153],in1956,mentionedthefollowingdrawbacksofiterativemethods:nearlyal