A node ordering algorithm to speed up the solution of sparse matrix and sparse vector linear equation systems

A NODE ORDERING ALGORITHM TO SPEED UP THE SOLUTION OF SPARSE MATRIX AND SPARSE VECTOR LINEAR EQUATION SYSTEMS Antonio G6mez and Leopoldo G. Franquelo Depto. de Ingen. Electrica, Electr6nica y Automatica Universidad de Sevilla, Spain ABSTRACT. Recently, mor e a tt e ntion hag be en do voted to spar ge vector mothoda in ord . ~ to r e duc e the comput a tion a l burden when aolvin~ sparae systems o! linear equatio n s. Theae methode exploit the sparsity of the independent vector and/or the deaire to know only a subset of tho unknown vector. They a re al a o a pplic a ble when ret a ctorization o f • s ll a htly modifi ed ma trix i . r . quir e d . This paper propOS8a a scheme to order the nodes with the purpoae o f reducing the number of operations when applying sparaB vector methoda. INTRODUCTION. Sparae matrix equatlonu of the form: Ax • b ( 1 ) a ppear 1n ma ny e n~ine e rin~ fi e ld s . Tho s tandard o olution procod ur e performs a ap a rsity - orianted LOU decomposition of A. followed by !o r ward a nd ba ck operationa On tho independent vector, b. Thl . Pa pe r d .a l . with two kind . of problemsl a) Repe a ted solution at (1) when mat r ix A 1s slightly modi!ied (parti a l ma t r ix r . t a ctori:etion problem) Ill. b) Solution ot (1) when either VQctor b ha D only a t ew non - zero elements or a small number or elements in the unknown vector x i8 needod (8p a r ~ e vector problem) [2l. lIS compeno~llon ~elhod •• the~e •• pecla are 8l.on~ly ralatad to r •• l op.r~tlon control ot .tacl.leal powar .yat.ma. A recant paper by Tinney.t .1. (2) emph •• ized the intareat or apar •• v~ctor ~.thod. 1n power .y.t.~ analyala, .hQwln~ a dramatic r.4u~tlon 1n oparatlona CQun~ co~p.r.d to convenllonal Method., In lh~l paper, lh. ~ulhor. noled lh~l naw be develop~d 1n order to enhanca the nod. orderlnl alcorlthma had to aparalty ot L1 <U1) without In this p.aper, pr.,)vlJ, .. .1 U)' Tinney' •• chama J (T-l) ordar1ne •• lao known •• mlnlmu" de~r~e .l~orllh~ [)) . BASIC CONCEPTS. Fo r almpl i city tht_ p. ~ .r will b. r •• tricted to .~·.r .. eymmelrle matri c es or mat.lea. that are aymm.trle In patlarn or non zero Given .. aymm8tric matrix A-<alJ) an ~'8oclaled undirected ,raph G=( V,£ ) can ba darined. ,\n,j t 1. ~h.re V ie the Ivt o( vertice. (Vl,v2'" .vnl r( unordered pair. of elamente of V (ad.ea), also called noda., point~, bu •••• ete, and other namee for adl.' al"'l broln c hes, olrCI or linea, If (Vi' vJ)E . £, than Vi an c. vJ are .aid to ba .,jJ.c~nt. Tho ,j.,rol ot a vertex 1e the numbar of v~rtlcaa adjacent to it. 11 C h a ~ n vertica •• than. one-to-ona map. t. trom V onto the .at 11.2, __ . ,n) 18 called a numberlnc ot C, rrd v ced &raph •• ~ocl~ t ad wilh lhe reduced matrix I" obtained (rom the o rlg1noll ,rolph by de ~ etln, vertex and incident a ' CI and adding arca J 11 batw •• n any palr ot vertic •• which .r. n.l~hbor. or nel,hbor. ot .ach olher . 1 but .r. not. Cone1d., the .ym~.trlc laclorlxatlon ot • apa ••• ~.trlx A into UlU. Tt,g ".ph a •• oclated to the m.trl~ r_ut+u ,_ called the filled ,".aph Gr- .ulutlun oC (1), 10111 .... ollli.r b 111 apar •• 'U' only .. t.w _lam_nle cd " .r. need.d. following (21 .o~e detlnltlona ral.ted to .perce vector. will be introduced In order to make the papar .elf-Mufflclent. A alncl.ton 1_. vector with only on. nonzero ele~~nt . ( •• ~. 1n location ~). A path (or a singleton ,_ defined .8 an ordered It&t oC rOWIl of U which .re atrictly neeea.ary {or the lorward solut.lon ot olgment ot X Is wanted. Such. path 1. • •• ily determined trom the aperae atructur. ot U as tollowa (21 : 1) Let k be the firat row 1n the path . 2) G.t the number of the 10w. A t-nu~bered nonzero ele~ent ! n row l:. ot U. Replacs k with this number and include it in the pat h. ) If k 1. the laat row, .x1t. Otherwis., return to step 2. Uhan row k of A 1. modified, graph at the singleton k-th ~uat only t.h. row. belon&:ir., b. taken into account to the path. dur in&" the r.factorization of A. Hance, partial ~atrix retactor1zation and torward .olutlon proca •• ara .bordad 1n the •• ma way. Pro. r.o~ on; only tha (or\folard and backward procc ..... ' on the ind.pendont vector will b. cona ldered. It only tha rowa of a ¥lven path are involved ln the solution ot (1) the corresponding proce8S la called the Faat Forward rllupecL lvlltly. (Ff) or At; iln example conulder the Iii node IEEE test &yate:n (41, who •• Inatr lx U til uhown 1n Fl~ u ro 1 .• . The ordarin£, alt c. r1t.hDl uae(l it! T-2, JI9 and node (the raterence noda In the Load Flow prob18~) 1. dlareaardod. A path craph for thla network. which compactly de.crib •• • 11 or it •• 1n~leton path. I .. ahown In Fleur. l.b. The ~r.ph 1 ... tr •• which h .... direction •• n •• (rom low to hleh nod. tor ff and from hLeh to low nod. (or fS. Thera 1_ a ralation.hlp between this path rraph and the aparalty structure of U-1, The nodee belonr!nr to the k-th noda path coincide with the nonzoro columma ot the k-th r ow of U1• H.trlx U1 (or tho formQr example 1_ rivan In FI,ur. l.c. A. may ba notad, the number of nonzero .lamente of U1 1. directly rel.ted to the aver.c •• 1n~1.ton path l.nath. Al~o the nu~b.r of nonzero .lement. of U 10 directly related to the .ver.~e mult-adds needed to perform the forward or back aUbatitution proce.s on .ach UESCRIPTION OF THE ALCORlnU1. The basic idea which motiv.ted the alzorithm is quite sImple. Lat Ua obeerve &&81n the T-2 order inc applied to tha l~-node ey.te~ ahown In ri~ure 1. In thi. ca •• tho av.ra~e path l.n~th of the tr •• 1. 4.92~ Thi. hi~h value 1e due ~alnly to the exi.tance of a lon~ branch consisting of e node. (2,3,4,6,9,11,12,13). A88ume now th.t tha s.me aystam 1. reordered •• can ba aeen In ficure 2. Tha resultant &voraz. path l.n~th Is 3. 61 and the lonse.t branch la compo8od only at $ nodo •• Th18 better r •• ult could be .xpected by _ .1~ple ins pec tion of the tree, where two aet. or nod.s are .pp~rent (encirclo d ) who.e p.lh. have only two common node •• Thl. shapa haa b.an achieved by uainc 8 clustarin¥ slcorllhm in order to obtain two waakly interconnected clueter •• Th. reduction in the avera,a path length impli.. a ~ore epar •• UI matrix . It may ba obeervad, however, that tht. 1. done at u.o coat ot a ell,htly lar,ar tIll-in ot U (one extra ele~ent appears). IN Honce, mollv~ted by the above reauIte, the procedure 18 propoaadl followlnc heuristic .) Perform a clusterine of the matrix A, which yields the typical Bordered Block 018£00_1 Form (BDOr) . The optimum numbar of eluatera 1s not ~nown -. prlori". In .anare1, 80me lri.l. muat be carried out, becau.a a larC8 nu~b.r of eluata.. may degrade aubatanttally lhe spar.1ty of U, overrldlnc lh. ,.1n ettained with. ahorta r path I.oath . So~.tl~.a. the ~.trlx atructure It,.lf aUle •• ta the number of eluatara to be adopted. b} Reorder lhe node. belon,!n, to .ach eluater follow!n, the minimum decree .l,orllh~ (T-2). A rew clustering algorithms have appeared In the lIterature (a.e lor ln~t.nco (5.6.7]). All of th.~ hav. the drawback of •• rlou.~y deEr.dln, t he .par.tty ot U, a. th_ .1~_ of the border crows up . Recently a clusterinc .l&orlth~ ha. b •• n proposed (Bl which has proved to ~vold th1s problem almoet completely . Thl. 1. the on. adopted in the ne ~l section. DISCUSSION Of EXPERIKENTAL RESULTS. Th. admltt.nc. ~atrlx at ~any electrical power eyetflme hee b.en used to te st the proposed alcorlthm. The resulte correspondin& to the 81Eht larger systems are tabulated tn Tebles I and II for the T-2 al.orlthm and the one propo.ed here r •• pectlv.ly. The " Appendix d •• crib •• briefly th. cheracterl.tlc. at s1ze. ranE. from 116 to 661 nod ••• a. ~ell •• the factorization of the ~.trlx (actually. the ~etrlx has one nod. le •• th.n the nu~b.r lndlc.ted In the flrat column ••• the ref.rence or .lack node Ie not included). For every po •• tble .Incl.ton the path lencth end the tot.l I 1/ i II II I I I I , ! I1UL -1 ADD HOD U U rAe 118 25) •• 0 425 175 399 2761 710 265 5<9 3622 912 29) 68' 5435 1229 )83 1038 8971 2503 ,,8 1189 10667 2~50 596 1710 15688 007 ~hl 18~1 17638 <4972 truL -1 ADO HOD U U rAe 118 256 968 436 175 <l3 1961 B8 265 552 30426 .87 293 121 396] 1414 38) 1048 T012 1602 "8 1197 8-41b ;1916 5'6 1714 1]819 055 661 1855 lS 3H 5;:'10 RASC O" SlNCLEi OX S CLU S TE R ED SI~CLETO~S I SINGL 2 SHICl .5 SINGt 10 SINC 2 SIHCL 5 SIHCl 10 SINC A? 1.01 loP AD AP AD A? AD AP AD AJ' AD AP AD '.5 21 1·4. 1 )) 25.1 62 35 . 9 88 10 . 6 2) 1] . 1 2' 17.5 ,0 16.9 50 22.6 66 33.2 9. 0.3 130 19.0 56 19.8 57 H . 2 68 1~.1 .. 21.3 : 10 .36.2 111 51.5 148 16 . 1 53 18.1 56 23.8 70 19.6 57 28.5 85 "".1 129 60.~ 175 20.1 56 23.6 68 29.8 ., 2~.5 137 31.~ 1 81 ~9.7 260 66.1 32<4 26.3 H5 28.2 H9 H . 6 173 2~.8 1.041 H.9 189 50.9 268 70 . 7 lH 25.8 14] 28.] 152 34.3172 27. 04 188 37 . 1 257 58.9 392 53.5 512 28.6 194 30.9 203 36.6 220 21. 7 190 40.3 278 61.8406 86.0 523 27.8 187 32 . 1 210 37 . 3 221 I Table I. Rc.ult. obtained with T-2 ~.thod . RANOOM SINGlETCNS ClDSTERED SINGLETONS 1 SINGL 2 SIHGL 5 SHiel 10 StNG 2 StHCt 5 SINGLo SIHC AP AD AP AD AP AD AP AD AP AD AP AD AP 1.0 .. ) 21 13.8 13 21 . 5 59 l5.~ 89 10.6 ' 14 12.2 27 11.7 <l 12.) 13 18.3 54 32 .0 .8 46 . 1 138 13.8 . 37 16.1 <l 10.8 56 14.0 <S 20.4 65 304 .9 110 50.8 149 1-4 . 6 ,. 17.5 53 22 . 7 65 13.6 ,2 21.8 72 37.9 130 58.1 196 15.2 ,7 16.8 ' 51 2l.9 6\ 19.4 .1 28.1 147 45 . 9 231 66,8 328 20.9 104 23.1 III 29.1 134 19.8 101 18.0 146 H . 9 24b 70.1 J4" 21.9 ill 23.6 11-4 29.6 IH 14 . 2 153 36 . 3 245 58 . 7 392 81 . 9510 25.3 162 18.7119 3~.9 102 24.2 IS6 36.6 20 60.739J 84.8 519 2(.8 155 1 9. 6 lB 35. 4 203 A~: Ave r .,e pith l~n'th. A O: Av era,e t ot al ~ult-.dd • . Tablt II. Rt.ult. obtalned wlth the pro poltd .l, o rltha. 01 R2 OJ .. 5< 12 8 H 56 H 12 II 5< 71 • 23 5< 72 8 26 57 11 13 28 56 70 12 25 56 68 11 23 55 68 10 21 ~ Rl .2 0) .. ~ I 54 H 8 25 9 ! S4 13 8 28 . , 5-4 H 8 27 2 53 72 6 18 \, 55 13 9 H 3 54 H 8 23 " 55 H 9 26 J 5~ J4 8 2' J ! J22 tabulated, •• well a. the ratlo. Rl. R2. A3. and R4 defined 1n (21 which elve & ~e •• ur. or the rel.tive advent_,e of uelo& rr lnet.ad or the lull forward proc •••• further te.t. war. ~.d. lnvolv!nc epara. vectora with two, tive end len r.ndo~ly cho •• n nonzero al.menta. for .ach c... 100 trlal. ware per(or~ed. and the avarac_ path lencth a. wall.. the avera,e lotal mult-add. 1n rr are tabul.ted here. From th... r •• ult. lh. ratios R5 and R6 defined 1n (21 may alao be computed. Th ••• rat loa indicato the loa. or .fficlency ot epar •• vector methode a. the number ~( random nonzer08 crowe. In practice, the nonzer08 1n the epar.. veclor are not randomlY chosen. To teat the .ffect. ot topolo11cally rel.ted nod •• another .at o( 100 trial. was done. Thi. t1me the two. rive anJ ten nonzero vl~~onl& of ll\~ sparae veclor were cho •• n 1n a .1mil.r way aa la done In dl~&onal b~nd ordoring. A nod a i. randomly chossn •• the rirst one. The adjacent nodes to those already numbered are conaecutlvely choaen. and so on unlil the required numb.r of nodas is achievod. The average reGults from lhe~. t.ale ar. aleo elven . It can be seen, •• pointed out 1n 121. that the growth 1n path the nonzoro enlrl.~ The last column in Table II ahowe the adopted number of clustors tor ~ach n~lwork. These results sugg.et the tollowin, conclueionsl The (ill-in o( lh. matrix U is slightly incr.aead with •• epect to T-2 al~orithm. as was expected (about l~). OpPosilely, the sparsity of 01 La ai&ni(icantly improved (about IS~) which means. a. wa. axplained previously, that the aver.ce path ~~ntth for ana 51ntlaton ia proportionally dacrs •• ad (column 5). Beslde&. the average total mult-adds in FF (or 1 81n~leton (column b) 1s about 20~ lecs than with T-2 algorilhm. , ,. J23 As the number of sin~leton. ~r ows, both a l~orlthma tend to behAv e similarly, thou~h (or 10 cluster e d .in~letong the propoaed & l~orithm st111 saves about 1~% ot mult-adds 1n ff co~p a r.d to T-2 (colu~ 18) • -When th~ aingletona a rs randomly chosen, the advant~ge o( the proposed algorithm over T-2 is las8 important. CONCLUSIONS. Recently, more interest hes boon devoted to op4C'Qe VQctor methode, · whlch enhance forward and backward a ubst1tut10n r~o=e==o= · b7 exploiting the spars1ty of the independent vector and/or tho need to know only a subset of ths unknown vector. The sarno tochnlque a con be usod In th e partial matrix ref a ctoriz a tion proco ~Q . Doth types of problems arise frequently In many eng1neering fields, particularly in electric power systems analysis. The speedup in a particular applicat10n dep en ds not only on tho numbor of nonzeroo in the voctor but on the eparelty of U and U1, which may be enhanced with a proper node ordering. In this paper, an a lgorithm is propoaed which clearly improves the sparsity ot U1 compared to the minimum de~ree alg orithm. The improvement 10 tranolated into a reduct10n on the operationa count bee ides 15:1:. REFERENCES. [1] - Chan S.M., Brandwajn V., Partial matrix refactorization. IEEE Transac. on PWRS-1, pp. 193-200, 1986. [2] -Tinney W.F., Brandwajn V., Chan S.M., Sparse Vector Methods. IEEE Trans. on PAS-104, pp. 29S-301, 1985. [3] -Tinney W.F., Walker J.W., Direct Solutions of Equations by Optimally Ordered Triangular Procee. IEEE vol. 55 pp. 1801-1809, 1967 Sparse Network Factorization. [4] - IEEE Committee Report, IEEE Reliability Tests Systems. IEEE Transac. on PAS-98, pp. 2047-2054, 1979.