IEEETRANSACTIONSONPOWERAPPARATUSANDSYSTEMS,VOL.PAS-89,NO.1,JANUARY1970Sparsity-DirectedDecompositionforGaussianEliminationonMatricesE.C.OGBUOBIRI,MEMBER,IEEE,WILLIAMF.TINNEY,SENIORMEMBER,IEEE,ANDJOHNW.WALKER,MEMBER,IEEEAbstract-Thisisaconcisecriticalsurveyofthetheoryandprac-ticerelatingtotheorderedGaussianeliminationonsparsesystems.Anewmethodofrenumberingbyclustersisdeveloped,anditsprop-ertiesdescribed.Byestablishingacorrespondencebetweenmatrixpattemsanddirectedgraphs,asequentialbinarypartitionisusedtodecomposethenodesofagraphintoclusters.Byappropriateorder-ingofthenodeswithineachclusterandbyselectingclusters,oneatatime,bothoptimalorderingandausefulformofmatrixbandingareachieved.Someresultspertainingtothecompatibilitybetweenoptimalorderingforsparsityandtheusualpivotingfornumericalaccuracyareincluded.INTRODUCTIONTHEORDERinwhichtheGaussianeliminationisperformedonsparsematricesaffectsthetotalnumberofnewnonzeroelementsgeneratedinthecourseoftheeliminationandhencethetotalcomputationtime[1],[2].Powersystemnetworkprob-lemsinvolvingcomplexvaluedmatricesoforder2000Urmorearenowbecomingcommon.Obviouslyitisnotpracticaltostoreandprocessthe8X106elementsofthesematriceswhich,typically,containonlyabout6X103nonzeroelements.Theexploitationofsparsitycannotbeoveremphasizedinthesecases.Recentinvestigationsoftheconservationofsparsity[3]-[161haveconsideredseveralpracticalorderingschemes.Therela-tiveperformanceoftheseschemescanbeconjectured,butwhatremainstobedeterminedaretheirinherentcharacteristicswhichwillaidinmakinganaprioriratingoftheirrespectiveefficiencies.Anotherareaofrelatedconcernisthatofmatrixpartitioningintoblocks(orsubmatrices)or,analogously,theproblemofnet-workdecompositionintoclusters[15]-[22].Apractialsolutiontothisproblemforlargerandommatrices(ornetworks)isstillanopenproblem.Mostresearchers,particularlythoseofdiakoptics[16]-[18],[21],tendtoassumethatsuchadecompositionisknowningeneral,oratleastgiven.Similarassumptionsareen-counteredinthedecompositionsforthesolutionoftheclassical"travelingsalesmanproblem"(TSP)[23],[24],wherethemethodofdiakopticsisalsoextensivelyused.Itisobserved[211,however,thattheoverallcomputationalefficiencyalsodependsontheactualdecompositionemployedinanysolution.Computationalefficiencyisgenerallygreatestwhenthetearingofnetworksiscarriedoutatregionsofminimumcoupling.Thistypeoftearingisthesubjectof[201,whereanoptimalschemeisdescribed.Thisschemeassumes,withoutlossofgenerality,thatalistofpreliminaryoptimaltearingisknownandthenproceedswithaniterativemethodusingcombinationallogictoobtainlargerclusters.ThisschememightPaper69TP2-PWR,recommendedandapprovedbythePowerSystemEngineeringCommitteeoftheIEEEPowerGroupforpresentationattheIEEEPICAConference,Denver,Colo.,May18-21,1969.ManuscriptsubmittedJanuary13,1969;madeavail-ableforprintingJune20,1969.TheauthorsarewiththeBonnevillePowerAdministration,Portland,Ore.97208.bequiteusefulinthepackagingofelectronicmoduleswhereeachmoduleconstitutesanoptimaltearing.Eventhenthecom-binatoriallogicwillrenderthemethodimpracticalforlargesystems.Decompositionintosubsystemsoftreeformisanotherrecentcontribution[22].Thismethoddoesnotyieldminimallyinter-connectedsubsystemsandhaslittletodowithsparsitysincesparsityhasneverbeenaprobleminGauss-Seideliterativemethods.Itdoesshow,asobservedin[23],thattheGauss-Seidelconvergenceisordersensitive,ifitconvergesatall.ForiterativemethodslikeNewton'swhichiswidelyacceptednow,thetearingphilosophyreportedin[22]isnotsparsityconservingandmayincreasesolutiontimes.JudgingfromexperienceinalliedproblemssuchastheTSP[24]-[28]thesubjectofoptimallyorderedGaussianeliminationappearsformidable.Buttoabandonfurtherconsiderationofthissubjectisneithersciencenorengineering.Consequently,theefforttoobtainpracticaloptimalorderingalgorithmsmustcontinue.Althoughcomputationallyinefficientat face value,theydopro-videastandardofperformancebywhichtheefficiencyofnear-optimalschemescanbejudged.Theobjectiveofthispaperwillhavebeenmetifithelpsthereaderto1)selectasuitableorderingschemewithoutfurtherexperimentation,and2)supporthisselectionwithsound,mathematical,physical,andeconomicreasoning.Theplanofthepaperisguidedbythefollowingconsiderations:correspondenceproblem:matrixpatternsversusgraphsasurveyofexistingorderingschemesnetworkclustersnetworkdecompositionintoclustersasequentialbinarypartition(SBP)onnetworksidentificationofclustersfromSBPorderingofclustersoptimalorderingmatrixbandingschemescomputationalresultsconclusions.MATRICES,GRAPHS,ANDNETWORKSInthissectionabasisisestablishedfordiscussingindistinguish-ably1)theGaussianeliminationonmatrices,2)variableelimina-tioninasystemofalgebraicequations,and3)nodeeliminationingraphsorelectricalnetworks.DefinitionAnincidencematrixMofamatrixYisdefinedtohavethefollowingproperties:(1,ifandonlyifyi1#0M,otherwise.141Authorized licensed use limited to: Iowa State University. Downloaded on September 4, 2009 at 14:42 from IEEE Xplore. Restrictions