Sparse Numerical Linear Algebra Direct Methods and

Sparsenumericallinearalgebra:directmethodsandpreconditioningIainS.DuyTechnicalReportTR/PA/96/22CERFACS42AveG.Coriolis31057ToulouseCedexFranceABSTRACTMostofthecurrenttechniquesforthedirectsolutionoflinearequationsarebasedonsupernodalormultifrontalapproaches.AnimportantfeatureofthesemethodsisthatarithmeticisperformedondensesubmatricesandLevel2andLevel3BLAS(matrix-vectorandmatrix-matrixkernels)canbeused.BothsparseLUandQRfactorizationscanbeimplementedwithinthisframework.Partitioningandorderingtechniqueshaveseenmajoractivityinrecentyears.Wediscussbisectionandmultisectiontechniques,extensionstoorderingstoblocktriangularform,andrecentimprovementsandmodicationstostandardorderingssuchasminimumdegree.Wealsostudyadvancesinthesolutionofindenitesystemsandsparseleast-squaresproblems.Thedesiretoexploitparallelismhasbeenresponsibleformanyofthedevelopmentsindirectmethodsforsparsematricesoverthelasttenyears.Weexaminethisaspectinsomedetail,illustratinghowcurrenttechniqueshavebeendevelopedorextendedtoaccommodateparallelcomputation.Preconditioningcanbeviewedasawayofextendingdirectmethodsorofacceleratingiterativeones.Wewillviewitintheformerwayinthistalkandleavetheotherperspectivetothetalkoniterativemethods.Finally,wewillbrieycommentonrecentattemptstodeveloptoolsandplatformstowardsasparseproblemsolvingenvironment.Keywords:Csparsedirectmethods,survey,BLAS,frontal,multifrontal,supernodal,minimumdegree,graphbisection,nesteddissection,parallelsolvers,preconditioning,sparse-leastsquares,sparselinearequations.AMS(MOS)subjectclassications:65F05,65F50,65F20.yAlsoatAtlasCentre,RAL,OxonOX110QX,England.e-mail:[e-mail]1Introduction12Highperformancesparsefactorization33Orderingsforsymmetricproblems54Solutionofsetsofsparseunsymmetricequations95Solutionofindenitesymmetricsystems106Sparseleast-squares117Parallelcomputing128Preconditioning159Towardsasparseproblemsolvingenvironment1910Concludingremarks20i1IntroductionIncommonwithmanyofmyco-authorsinthisvolume,mystartingpointwastoreadthereviewonthissubjectgivenatthelastStateoftheArtmeetinginBirmingham.Thearticle\SparseMatriceswasauthoredbyJohnReid,anditisperhapssignicantthatitcoveredbothiterativeanddirectmethods,thesubjectoftwotalksatthismeeting.Indeed,althoughIhavebeenworkinginthiseldforabouttwentyveyears,Inditamazinghowmanyadvanceshaveoccurredinthelastten,necessitatingtheduallecturesofthismeeting.Althoughthispaperisprimarilyondirectmethods,Ialsoincludeasectiononpreconditioningtechniquesforusewithiterativemethods.TheviewpointofthisdiscussionwillbequitedierentfromthatpresentedinthechapteronIterativeMethodssinceIwilllookattheconstructionofpreconditionersasbeinganalternativetodirectmethodswhen,foronereasonoranother(usuallystorage),directmethodsareinfeasible.Moreover,incommonwithproponentsofiterativemethods,Ifeelstronglythattheonlywayofsolvingreallychallenginglinearalgebraproblemsisbycombiningdirectanditerativemethodsthrougheitherconventionalornovelpreconditioning.AlthoughIintendthispapertobeageneralStateoftheArtsurvey,IwishtoemphasizewhatIconsidertobethemostimportantdevelopmentsofthelasttenyears.Accordingly,Ihavestructuredthetexttohighlight:implementationsthatusehigherlevelBLASkernels,advancesinorderingstrategiesparticularlyforsymmetricproblems,theexploitationofparallelism,andtheuseofdirecttechniquesaspreconditionersforiterativemethods.Undoubtedly,thekernelthatgetsclosesttopeakperformanceonmoderncomputersisadensematrix-matrixmultiply.AstandardversionofthiskernelisprovidedbysubroutineGEMMintheLevel3BasicLinearAlgebraSubprogramsorBLAS(Dongarra,DuCroz,DuandHammarling1990)andissupportedbymanyvendorsofhighperformancecomputers.Mostsparsedirectcodesusethisandalliedkernelstoachievehighperformance,andwediscusshowtheyareabletodothisinSection2.Tenyearsago,onemighthavebeenforgivenforthinkingthattheproblemoforderingasymmetricsystemforsubsequentGaussianeliminationwasresolvedinfavourofminimumdegree,oneoftheearliestproposedorderings.However,quiterecentlytherehasbeensignicantworkondevelopingotherclassesoforderings,relatedtodissectionmethods,whichareshowinggreatpromiseofoverhaulingthisperceivedwisdom.Additionally,therehasbeenfurtherunderstandingoftheminimumdegreeorderingandattemptstomakeitmoreecientandtoadaptitfororderingsmoresuitedtoparallelcomputation.WediscussorderingsforsymmetricsystemsinSection3.In1986,therewaslittlesoftwareforunsymmetricsparseproblems.EarlyexamplesincludedNSPIVbySherman(1978),Y12MbyZlatev,WasniewskiandSchaumburg(1981),MA28,MA32,andMA37fromtheHarwellSubroutineLibrary(HSL)andasurrogateMA28intheNAGLibrary(F01BRF/F01BSF/F04AXF).Thedevelopmentandproductionofsparseunsymmetricsolvershasnowbecomeaveritablegrowthindustry.Themultifrontalandsupernodaltechniques,sopowerfulinthesymmetriccase,havebeenextendedtounsymmetricsystems.Inotherapproaches,variousdecompositionalandpreorderingtechniquesareusedtofacilitatelaterfactorization,particularlyonparallelcomputers.WeconsidertheseissuesinSection4.WediscussthecaseofsparsesymmetricindenitesystemsinSection5andthesolutionofsparseleast-squ