New Parallel Algorithms for Direct Solution of Spa

NewParallelAlgorithmsforDiretSolutionofSparseLinearSystems:PartI-SymmetriCoeÆientMatrixKartikGopalanC.SivaRamMurthyDepartmentofComputerSieneandEngineeringIndianInstituteofTehnologyMadras600036,Indiae-mail:murthyiitm.ernet.inAbstratInthispaper,weproposeanewparallelbidiretionalalgorithm,basedonCholeskyfatorization,forthesolutionofsparsesymmetrisystemoflinearequations.Unliketheexistingalgorithms,thenumerialfatorizationphaseofouralgorithmisarriedoutinsuhamannerthattheentirebaksubstitutionomponentofthesubstitutionphaseisreplaedbyasinglestepdivision.Sinethereisasubstantialredutioninthetimetakenbytherepeatedexeutionofthesubstitutionphase,ouralgorithmispartiularlysuitedforthesolutionofsystemswithmultipleb-vetors.Theeetivenessofouralgorithmisdemonstratedbyomparingitwiththeexistingparallelalgorithm,basedonCholeskyfatorization,usingextensivesimulationstudies.InPartIIofthispaper,weproposeanewparallelbidiretionalalgorithm,basedonLUfatorization,forthesolutionofgeneralsparsesystemoflinearequations,havingnon-symmetrioeÆientmatrix.KeyWords:LinearEquation,SparseSymmetriSystem,CholeskyFatorization,ParallelAlgorithm,BidiretionalSheme,Multiproessor.1IntrodutionTheproblemofsolvinglargesparsesystemsoflinearequationsarisesinvariousappliationssuhasniteelementanalysis,powersystemanalysis,andiruitsimulationforVLSICAD.Authorfororrespondene.1Inthispaper,weonsidertheproblemofsolvingsparsesymmetrisystemoflinearequationsoftheformAx=b,whereAisasparsesymmetrioeÆientmatrixofdimensionNN,andxandbareN-vetors.Traditionally,theproessforobtainingthediretsolutionforasparsesymmetrisystemoflinearequations,Ax=b,involvesthefollowingfourdistintphases.Ordering:ApplyanappropriatesymmetripermutationmatrixPsuhthatthenewsystemisoftheform(PAPT)(Px)=(Pb).Symbolifatorization:Setuptheappropriatedatastruturesforthenumerialfa-torizationphase.Numerialfatorization:DeterminetheCholeskyfatorLsuhthatA=LLT.Substitution:DeterminethesolutionvetorxbyrstsolvingtheforwardtriangularsystemLy=bandthensolvingthebakwardtriangularsystemLTx=y.Forsolutionofmultipleb-vetors,therstthreephasesarearriedoutonlyonetoobtaintheCholeskyfatorL.Thesubstitutionphaseisthenrepeatedforeahb-vetorinordertoobtainadierentsolutionvetorxineahase.Thus,inproblemswhihinvolvesolutionofmultipleb-vetors,thetimetakenbyrepeatedexeutionofsubstitutionphasedominatestheoverallsolutiontime.Anyparallelformulation,whihanreduethetimetakenbythesubstitutionphase,willontributesigniantlytoenhanedperformaneoftheentireproess.AlthoughtraditionalapproahestoparallelsolutionofsparsesymmetrisystemoflinearequationshaveyieldedeÆientparallelalgorithmsforthenumerialfatorizationphase[1,2,7,11,15,21℄,notmuhprogresshasbeenmadeintheaseofsubstitutionphaseduetothelimitedamountofparallelisminherentinthisphase.Moreover,theforwardandbakwardsubstitutionomponentsofthesubstitutionphaserequiredierentparallelalgorithmsduetothemannerinwhihdataisdistributedovervariousproessors.Existingworkonparallelformulationsforthisphaseanbefoundin[6,12,14℄.InPartIofthispaper,wepresentanewbidiretionalalgorithm,basedonCholeskyfatorization,forthesolutionofsparsesymmetrisystemoflinearequations.Inouralgo-rithm,thenumerialfatorizationphaseisarriedoutinsuhamannerthattheentirebaksubstitutionomponentofthesubstitutionphaseisreplaedbyasinglestepdivision.Thebidiretionalalgorithm,basedonLUfatorization,forthesolutionofgeneralsparsesystemoflinearequations,ispresentedinPartIIofthispaper.Theappliationofthenoveloneptofbidiretionaleliminationtodenselinearsystemsanbefoundin[19,20℄.2Therestofthepaperisorganizedasfollows.Insetion2,wepresentthebidiretionalsparseCholeskyfatorizationalgorithmforsparsesymmetrimatries.Insetion3,wepresentthebidiretionalalgorithmforthesubstitutionphasewhihdoesnothaveabaksubstitutionomponent.Insetion4,wedevelopabidiretionalheuristialgorithmfororderingonthelinesofthepopularnesteddissetionorderingalgorithm[4,5℄forsparsesymmetrimatries.Insetion5,wedesribeasymbolifatorizationalgorithmwhihsetsupdatastruturesrequiredbythebidiretionalCholeskyfatorizationphase.Insetion6,weevaluatetheperformaneofthebidiretionalalgorithmonhyperubemultiproessorsandpresentomparisonofouralgorithmwiththeexistingshemebasedonsparseCholeskyfatorization.Insetion7,weonludethispaperwithsomeobservationsaboutpossiblefutureimprovementstothebidiretionalsheme.2TheBidiretionalSparseCholeskyFatorization(B-SCF)AlgorithmUnliketheregularCholeskyfatorizationalgorithmwhihfatorizesAtoobtainthelowertriangularmatrixL,suhthatA=LLT,theBSCFalgorithmfatorizesAintoaseriesoftrapezoidalmatriesofmultipliers.Thisseriesoftrapezoidalmatriesremovetheneedforthebaksubstitutionomponentinthesubstitutionphase.Inthissetion,werstpresentanoverallviewoftheoneptofbidiretionalCholeskyfatorization.WethenproeedtodesribethemannerinwhihthesparsityoftheoeÆientmatrixanbeexploitedtoobtainhigherdegreeofparallelism.FollowingthiswepresentthedetailsofimplementingBSCFalgorithmonmultiproessorsystems.2.1BidiretionalCholeskyFatorization-TheConeptInregularCholeskyalgorithm,thelowertriangularmatrixLisobtainedbyhoosingolumns1throughNo