An efficient ordering algorithm to improve sparse vector methods

AN EFFICIENT ORDERING ALGORITHH TO IMPROVE SPARSE VECTOR KKTHODS A. Gomez Member IEEE Dep. de Ingenieria Electrica L.G. Franquelo Member IEEE Dep. de Ingenieria Electronica, de Sistemas y Automatica Univ. de Sevilla Spain Keywords: Sparse Techniques, Ordering Algorithms, Linear Equations. Abstract. This paper presents a new node ordering algorithm to enhance sparse vector methods. The proposed technique locally minimizes the number of non-zero elements of the inverse of the table of factors. It uses the cardinality of the set of nodes which precede each node in the path graph as a tie-break criterion in the minimum degree elimination process. Test results are included showing that the method performs better than previously published methods. INTRODUCTION. A great deal of Sparse Matrix problems still represent a challenge for Electrical Engineers, especially if the large scale of these problems and real-time requirements are considered. Nowadays, advances in computer hardware and development of efficient algorithms permit to afford certain problems that only a few years ago did not seem to have a practical solution. Sparse Matrix techniques introduced in the sixties [1] had a great transcendence in the efficient solution of the power flow problem. More recently, Sparse Vector techniques were introduced to speed up a number of important power system problems [2]. Two kinds of papers can be found in the literature related with these topics: Basic developments and applications. Among these, reference [3] can be mentioned, where two Partial Refactorization methods are applied to Newton Load Flow, Fast Decoupled Load Flow and Security Analysis. Other recent papers related to applications deal with the following problems: Parallel Inversion of Sparse Matrices [4), Fault Analysis [5) and Linear Contingency Analysis [6]. The first kind of papers are devoted to the development of algorithms and basic concepts that permit to get better performances when these techniques are applied to particular problems [2, 7-9). This paper falls under presents a new ordering application. this category because it algorithm of general RBVIEV OF SPARSE VECTOR CONCEPTS. Consider the solution of the equation: (1) where A is sparse. If we restrict ourselves, for simplicity, to the case in which A is symmetric and positive definite (e.g . the matrix B' in the Fast Oecoupled Load Flow), then A could be factorized as UtU . Once this requisite has been fulfilled, the standard forward and backward operations on the independent vector give the desired result, x. In this paper the attention is focused on two kinds of problems: a) Solution of (1) when either vector b has only a few non-zero elements or a small number of elements in the unknown vector x are needed (Sparse Vector problem) . b) Repeated solution of (1) when matrix A is slightly modified (Partial Matrix Refactorization problem) • It is a common practice to use an undirected graph associated to matrix A so that the elimination process can be easily visualized. Each time a row in A is eliminated, the graph must be updated by deleting the corresponding vertex and incident arcs and adding the required fill-ins, giving the reduced graph at this stage. Also, a filled graph may be associated to the matrix U+U t which depends, obViously, on the ordering adopted during the elimination process, i.e., on the number of fill-ins generated. As an example, consider the 10-node system shown in Figure 1. The structure of the resultant U matrix is shown in Figure 2, when the Minimum Degree strategy (MD) is adopted. The leftmost column indicates the order in which the nodes have been eliminated. 5 Fig. 1. 1O-fude Systan. 1234567890 5 1X X 1 10 2 x x 1 4 3 xx X 2 7 4 X 0 X 2 X: Orlginal eleoent 2 5 XXX x 3 o : Fill-in elEllle!lt 1 6 XXXX 3 3 1 XOOX 3 6 8 xxx 2 8 9 xx 1 9 10 X 0 Fig. 2. Structure of U. For both problems formerly interesting to introduce, moreover, following [2]. mentioned it is other concepts, First of all, non-zero element singleton is an follows: a singleton is a vector with only one (e.g. in location k). A path for a ordered list of rows of U defined as 1) Include k in the path. If k is the last row of 0, exit. 2) Replace k with the first non-zero column in row k of 0, and go to step 1). If b is a singleton, then only the rows of its path are needed during the forward elimination process. Analogously, if only the k-th entry of x is wanted, only the rows of this path are strictly required during the backward substitution process. In this case the path is swept in the reverse order. These processes are called the Fast Forward (FF) and Fast Backward (FB) processes respectively. Taking into account the analogy between factorization and forward elimination processes, it is clear that only the rows involved in the appropriate path should be updated in 0 when the k-th row of A is modified (Partial Matrix Refactorization, or simply PHR). A path graph may be built by union of all possible singleton paths. Figure 3 shows the path graph for IlI8trix 0 in Figure 2. The appropriate subset of this tree determines the rows involved in FF, FB or PMR processes when b has several non-zero elements, more than one element is wanted in x, or various rows are modified in A (provided in this case that the structure of 0 remains the saae). Each row of 0 with d non-zero ele~ents contributes with dt mult-adds in t~e FF/FB process and di (d t +l)/2 in PMR. There is an interesting relationship between this path graph and the structure of 01 which is the key -for the development of more efficient orderinf algorithms. The non-zero columns of the k-th row of 0give the path for the node at k-th position. 10 5 1 3 6 8 9 4 2 Fig. 3. Path Graph of the 10-N:x1e Systen. Conversely, the non-zero rows of the k-th column of 01 give the subset of the tree' which precedes the node at this position. Figure 4 shows the S:tructure of 01 for the same earlier examplei and viSualizes the mentioned relationship between 0and the path graph for the case of.node 1 which is numbered at 6 th position. 1234567890 5 lX' XXXXX 10 2 X X XXXXX 4 3 XX XXXXX 7 4 X XXXXX 2 5 XXXXXX 1 6 XXXXX 3 1 XXXX 6 8 XXX 8 9 XX 9 10 X Column of node Fig. 4. Structure of U1 and RelationShip with the Path Graph. From the preceding comments it is clear that the number of non-zero elements of ur 1 is a measure of the average singleton path lenfth. Actually, the number of non-zero elements iD ur (including the diagonal) divided by the number of nodes gives the average singleton path length. Also the number of non-zero elements of 0 is a measure of the average number of mult-adds required to perform the FF/FB or the PKR proceSS. Bence, what is required is that both 0 and ur 1 remain as sparse as possible. Sometimes, a less sparse o is permissible if this is counteracted by the saving achieved in ur 1• KOTIVATIOH AND DESCRIPTION OF THE ALGORITBK. In order to allow comparisons the KD algorithm (or Tinney's second scheme) will be first described. This description will be somewhat conventional as the actual computer implementation will depend strongly on the storage-accessing scheme adopted (e.g., steps 4 and 5 below could be probably merged into ' only one step). For this purpose the next vectors will be used: f(i) : Position of node i in the final ordering. Initially set to zero; f(i).O means that node i has not yet been considered. 0(1) :. Degree of node i in the reduced graph. Initially set to the degree in the original graph. Then, for a graph with N nodes: Minimum Degree Algorith. (MO): 1) Let It-!. 2) Pick up a node i with f(i)=O such that Dei) is minimum. The ties are brakeD arbitrarily, although for programming convenience, the first or the last eligible node in the natural order is usually choseD. Set f(i)=k. 3) If k equals H then stop. 4) For each j adjacent to i such that f(j)=O, set O(j )_O(j)-l. 5} For each pair of nodes a, n adjacent to i but not adjacent to each other, such that f(.)=f(n)=O, create a new edge joining a and n, and increase O(m), OeD) in one unit. 6) Set k-k+l and go to. step 2). The main weakness of this algorithm is the large number of ties which appear in step 2). The way these ties are broken may Dot have a strong influence on the sparse structure of U [10], but this is not the case when U1 or, equivalently, the average path length is considered. For instance, the average path length for the 118-node IEEE test system is 9.46 when the first minimum-degree node encountered in the natural order is chosen. This value rises to 11.77 when the last eligible node is taken. Examples could be found where just the opposite would happen. That is, the behaviour of the MD strategy, as far as the efficiency of sparse veetor methods is concerned, depends strongly on the natural order of the nodes, which is not a desirable feature (see Comparative Results). Reeognizing this faet three st!:ategies were ploposed in reference [7] intended to enhance the spa!:sity of ur 1 without sacrificing the sparsity of U, by simply using a second criterion to break the ties which appear during the execution of MD algorithm. Among these strategies, Algorithm I (AI) seemed to be the best one. When a tie appears, it numbers in the first place the node with fewer adjacent nodes which have been already elimina ted. More precisely, when more than one node has a minimum degree in the reduced graph, the one with a minimum degree in the filled graph is first eliminated. As an example consider Figure 5. In the reduced graph there are 2 nodes with a degree of 3. Node b is first chosen by Al because it has 3 adjacent nodes in the set of eliminated nodes, against node a which has 4 of such nodes. More recently [8], a new algorithm has been proposed which t!:ies to improve the MD strategy in a similar way. This algorithm, which is called Minimum Degree, Minimum Length (MD - ML), uses the concept of the depth (or the length) of a node in the path graph, which is updated very easily. The MD-ML algorithm is also described in the discussion and closure of [7] where a preliminary and brief comparison is made with AI. Figure 6 shows the path graph for the 10-node system when the logic of Al is used, while Figure 7 shows the same example following the MD-ML strategy. In this particular case Al gives a shorter average path (3.2) than MD - ML does (3.7), though, in general, the MD-ML st!:ategy performs bette!: than AI. Once these two algorithms have been revised, the rest of the section will be devoted to the new algorithm proposed in this paper. Consider once more the lO-node system when nodes 1, 8 and 9 remain to be eliminated and the other nodes were eliminated in the order 5, 10, 4, 7, 2, 6, 3. Figure 8 shows the filled graph under this situation. Three fill-ins have been generated. Figures 9.a, 9.b and 9.c show how the path graph would grow if nodes 1, 8 and 9 respectively were 5 10 4 7 2 6 3 9 8 1 eliminated nodes \ I I I ) f i lled graph Fig. 5. Sample Illustrating the Logic of AI. 1234567890 Ix X 0 2 X X 0 10 6 3 XX X 0 4 X XO 2 5 X X XX 0 6 X XXX 0 7 XXOX 1 8 XXO 2 9 XX 5 10 X 8 Fig. 6. Struc=e of U and Path Graph Foll~ Al. eliminated at this point (the degree of all of them is 2). In this situation the MD-ML strategy would not be useful since the length is 2 in all three cases. The squa!:ed nodes are the set of already-eliminated nodes which are adjacent to the node in hand, i.e., the cardinality of this set is used as a tie-break criterion by AI. Hence, node 9 should be chosen firstly if this strategy were adopted. Notice that this set of nodes represents the non-zero rows in the corresponding column of U (see, for instance, the last three columns in Figure 6). However, the nodes inside the closed 1234567890 2 5 IX X 0 10 2 X X 0 4 3 XX X 0 7 4 X OX 1 2 5 X XXX 0 6 6 X XXX 0 3 7 XXOX 1 1 8 XXO 2 8 8 9 xx 3 9 10 X 4 9 depth=4 Fig. 7. Structure of U and Path Gra\Yl FollCllli~ MD-ML. Fig. 8. Filled Graj:tlllefore Nodes 1, 8 and 9 Have Been Eliminated. 00 5 ylO 4 6t!] /2 , 7 / " /" 3 , / .... ", 5 • (al 6 ij] r I length=Z 2 wlI length=2 VWI 9 (f 1 ength=2 (c) Fig. 9. Growth of the Path Graj:tl under Tht:ee Different Hypothesis. ,curve represent the non-zero rows in the same column of 0- (remember Figure 4). Obviously, the squared nodes are always included within the closed curve, as the structure ' of U is a . subset of the structure of 01• Vhat we are proposing is to use . the cardinality of this new set, i.e., the set of nodes which precede the node under consideration in the: path graph, as a tie-break criterion. This i~ equivalent to locally minimize the number of nor-zero eleml!!nts in 01 and, hence, better results are expected. The only drawback of this method is that this set is more difficult , to coapute or update than the parameters used bY ' competitive algorithms. Following this new strategy, nOoe 9, is also the first to be eliminated. The ' reSUlting path graph is shown in Figure 10 where the precedinJ sets for nodes 1 and 8 are abo outlined. It is clear that the next node to be chosen is node 8, leaving node 1 at .the bottom (see ' the final resul t in Figure 6) • . , A careful analysis of the changes produced from Figure 9 to , Figure 10 will provide us with a method to update . the preceodiilg set each tille a node is ' eliminated . . Let us deUne the foiiowing vectors: P(i) : Number , of nodes in the path graph which precede node ' 1 (plus one to incl~de 1 itself). Initially set to one. ' F(i) : Bpolean variable. It is ~ true' if node i is the last node added to any connected COmponent of the pa th graph, 1. e. , if node i i,s a bordering (or frontier) node. Initially set to 'false'. The importance of bordering nodes is that it is only required to know P(k) for such nodes. For instance, in Figure <:I nodes 3, 5, 6 and 7 are bordering nolles and P(3)z2, p(5)ml, P(6)=l, P(7):3. , It is immediate to see that: ' P(1)-P(3)+P(5)+P(6)+P(7)+1-8 P(8).P(3)+P(6)+P(7)+1_7 P(9).P(3)+P(6)+1.4 Let us now retul:n to Figure 10 whel:e node 9 is a new bordering nolle and nodes 3 and 6 have left this set of nodes. O!>serve that the new values of PO) and peS) can be updated as follows: . P(1)~P(1)+P(9)-P(3)-P(6)-9 P(8)_P(B)+P(9)-P(3)-P(6)=B These considerations lead finally to the following algorithm (see Appendix for a practical implementation). For a graph with. nodes: Minimum Degree. Klniawa Humber of Predeceossors Algorithm (KD-KNP). 1) Let kat. 2) Pick up a node i with f(i)~O such that D(i) is minimum. Break the ties which appear in this process selecting the node with minimum P(i). Set f(i)-k, F(i)-'true'. . 3) If k equals H then stop. 4) For each j adjacent to i in the filled graph 00 the follOwing: 4.1) If [(j)-O then set P(j).P(j)+P(i), D(j)zO(j)-1. 4.2) If F(j)-'true' then set F{j)-'false' and for each m adjacent to j such that · f(a)_O do P(a)=P(.)-P(j) . 5) For each pail: of nodes a, 0 adjacent to i but not adjacent to each other, such that f(a)~f(o)aO, create a new edge joining m and D, and increase D(m), 0(0) in one unit. . 6) Set kak+1 and go to step 2). Figure 11 shows the, results of applying this algorithm to the 10-node system. The SaDe avel:age path length as in Al is · obtained though the resultant ordering is different. Nodes preceding node 1 1 ength=3 Nodes preceding node 8 Fig. 10. Path GIajn Before NodeS 1 and 8 !lave Been Eliminated. 1234567890 10 IX X I 5 2 X X 1 10 4 3 XX X 1 7 4 x xo' 3 9 5 x XXX 1 2 6 it XXX 1 6 7 XOXX 2 3 8 XOX 4 8 9 xx 8 1 10 X 10 Fig. 11. Structure of U and Path GraIn Foll~ IO-IH'. orDBR POSSIBLE VERSIONS. 2 In view of the proposed algorithm, some modifications may 'be intuitively introduced which should lead eventually to \ further improvements. For instance :, instead of using P(i) as a merit factor, 5(i) could be used, where SCi) is defined as the addition of all possible path lengths from the nodes which precede node t, like in Figure 12.&. Figul:e 12.b shows how node b should be chosen following this new criterion while node a is preferable from the point of view of MD-MNP strategy. This version which may be called ' Minimum Degree, Minimum Total Path Length (MD-HTP) differs from the main version in ' what follows: The ties in step 2) are brOken by means of S(l) which is initially set to zero. In step 4), each time P is updated, 5 must be also recomputed, depending on the case, as follows: 4.1) S(j)_S(j)+(P(i)+5(i» 4.2) 5(a)=S(m)-(P(j)+S(j» That is, this version uses P only as a means of easily updating S. By using any of the , algorithms described or revised until now, a large number of ties still appear in the second criterion. In order to decrease such a 1al:ge number of draws, it is possible to use the mean path, computed as the real value S(i)/P(i), in step 2). Another way of decreasing the number of ties could be by using a third criterion. Among others, the following ones can be mentioned: KP-HNP-ML, HD-HNP - HTP (a) (b) Fig. 12. Illustration of the It>-M1'P Strategy. and MD - MNP-Maximum distance appart from the centre of the graph. Unfortunately, these more complex strategies have not yielded good enough results, when they are applied to our networks, to be further considered. Finally, a refinement of the MD-MNP strategy stands out which is based on the following reasoning: Assume you are interested in minimizing the total mult-adds required in the FF/FB process. When node k is involved in a singleton path it contributes with D(k) mult-adds. Considering that node k appears in P(k) paths, its overall contribution is D(k).P(k) multadds. So it seems logical to use the product P.D as a merit factor. However, using this product as the main ordering criterion causes a large number of fill-ins in U because the MD strategy is perturbed. It would be interesting, then, to find a compromise solution between this strategy and MD-MNP. In this sense, MD-MNP could be modified so that a small difference in D is less important than a big difference in P. Formally: once a minimum degree node k is considered as a candidate in step 2), choose a node j which satisfies D(j)<D(k)+h and P(j).D(j) is as small as possible. When h -ranges from 1 to 4 better results are obtained as may be seen in the next section. Typically h=3 gives the best results. COMPARATIVE RESULTS. Appart from the tutorial examples used in previous sections, other real systems, including the IEEE test systems and several larger Spanish networks, have been tested [9]. Tables I, II and III summarize some of the results obtained with MD, MD - ML and MD - MNP algorithms respectively for four selected networks. Each table contains the following items from left to right: Size of the system (nodes)I number of nonzero off - diagonal elements of U and ur , mult-adds required in the full factorization process, ordering execution time and, finally, the average and standard deviation, for every possible singleton, of the path length, mult-adds in the FF/FB and mult-adds in the PMR process. Actually, the results refer to B' matrix and, therefore, the slack node is not included. Figures 13 and 14 compare the savings obtained by A1, MD-ML and MD-MNP with respect to MD when they are 50 -1 Opr. TinE PATH OPffi.FF/Fl 0Pffi. 00 thI U U Fac. sec. Mean SO Mean SO Mean SO 118 253 990 425 0.15 9.46 2.6 21.11 7.2 40.09 15.0 265 549 3622 972 0.63 14.72 3.8 48.84 12.4 132.97 36.1 448 1189 10667 28!:O 1.96 24.86 6.9 140.68 41.3 563.70 162.4 661 1851 17638 4972 4.18 27.72 8.6 189.62 72.1 900.90 367.7 Table I. Results obtained with MD (T-2) method. -1Opr. TinE PIilll OPffi. FF IFB OPffi. H1R thI U U Fac. sec. Mean SO Mean SD Mean SO 118 251 893 419 0.18 8.63 2.1 1B.04 6.2 33.37 14.2 265 549 3002 983 0.80 12.37 3.5 37.74 15.6 99.15 48.2 448 1180 9475 2755 2.30 22.20 6.7 100.82 37.1 378.53 130.0 661 1830 15746 4778 4.92 24.86 6.8 152.18 49.4 781.00 1B9.7 Table ll. Results obtained with MD-ML method. -1Opr. TinE PIilll OPffi. FF IFB OPffi. H1R lbl U U Fac. sec. Mean SD Mean SO Mean SO 11B 251 805 419 0.20 7.88 2.1 15.93 6.5 29.01 14.8 265 548 2870 977 0.83 11.87 2.8 33.71 10.9 83.46 38.7 448 1179 7667 2761 2.35 18.15 4.6 B3.87 23.7 289.52 86.2 661 1799 14634 4514 4.83 23.17 5.7 129.14 38.4 518.60 174.9 Table Ill. Results obtained with MlJ...WI' method. applied to these systems. The figures show clearly that the method proposed in this paper (MD-MNP) is superior to MD-ML which is the best algorithm published up to date. In table IV the average savings achieved with a larger number of networks are presented. Again, it can be seen that the proposed algorithm yields better results than previous methods for the three items considered. Notice that even a slight improvement can be attained by using the refined version described earlier. Observe also that the largest savings are Mean Number Ooerations Method Mean Path FF/FB Par t. Re fac t. A1 ref. [7] 5.63 12.75 17.28 MD-ML ref. [8J 12.33 20.89 26.60 MD-MNP 19.70 32.01 39.71 Refined MD-MNP 25.66 35.56 40.88 Table IV. Savings with respect to MD (X). 350 40 C=:J ND-NL _MD-MNP C=:JAl C=:J ~1D-~lL _ND-NNP C=:JA1 300 I --- 11inim. Degree ~ - -- -- Propo£"d r1"thod ~ " v i:I 30 -- E ..., '- .30 ..., 3 ,~ 2513 ~ r :3 20 '" c ... > II' (/) 10 I j L I::lJAL- .l' ~LAJ ~ l ~ 150 <I I ..., -; 100 E 50 o 448 Nodes 2 3 4 2 3 4 25 50 No. o~ Singletons Fig. n. Saving in FF/FB w.r. t. MD. Fig. 14. Saving in 00 w.r. t. MD. Fig. 15. Mult -Adds in FF IFB. obtained in the PHR process (the rightllOst column) as may be expected, since the non-zero elements of any row involved in the path contribute quadratically to the overall operations count of this process while only linearly to the FF/FB process. As the number of singletons grows, the advantage of using sparse vector methods decreases. When this number tends to the size of the system, the average number of mult-adds required in the FF/FB approach the second column of the tables (i.e., the number of non-zero elements in U). This fact may be seen in Figure 15, where the proposed algorithm (HD-KNP) is compared to HD for as many singletons as approximately a 10% of the network's size (in this case the 448-node system). Analogously, as the number of modified rows in the matrix increases, the use of PMR techniques is less useful. Now, the required mult-adds tend to the fourth column of the tables (operations count in the full process). ,Figure 16 illustrates how tbe HD-KNP method behaves compared to MD for the same network. In both figures, the operations count was computed from a total of 100 trials except, logically, for one singleton. As was cOlDIDented in a previous section, the behaviour of the MD strategy, as far as the path length is concerned, has a strong dependence on the natural order of the buses. Consequently, the performance of this metbod may be, in certain cases, almost as good as that of tbe proposed algorithm and very poor in otber cases. However, tbose methods wbicb use a second criterion have a more regular behaviour. To prove tbis assertion a simple test has been done . consisting in generating randomly four ditferent node orderings for several networks. Figure 17 shows the results of this test for the l18-node system. The black bar refers to the natural order while the white ones correspond to the four random orders. It is apparent that the proposed method (HD-KNP) is quite insensitive to the way the nodes are ordered whereas, in the other extreme, HDproduces notably disperse results in spite of the small size of the test case considered. Execution times of the proposed algorithm (Table III) are only slightly larger than those of the MD algorithm (Table I) though they depend on the efficiency of the impleeentations (see Appendix). These tiaes were obtained on a pVAX-II. Finally, though the aim of this paper is not to present specific applications, it aay be interesting to point out that about a 15% reduction in the execution time has been achieved when MD-HNP is applied to the parallel solution of linear equations (e.g. those which appear in the Fast Decoupled Load Flow). 1000 809 til ~ 600 <I I .jJ .... £ 400 --- Minim. Degree ----- Proposed !'Ietho o 25 50 No. oT ~lodiTi.ed Rows Fig. 16. Ihl t-Mds in 00. 118 Nodes MD-tIL I1D-MNP 2::i L-. _____ il.lL-_..LlJ~ ____ lll.LL __ _ 2 3 Alsorithm Fig. 17. Ihlt-Mds in 00 for DifferEnt ~. CORCLUSIORS. In this paper a node ordering algorithm to enhance sparse vector .. thods is presented. The method proposes a way to ' break the draws which appear during the choice of the pivot in the elimination process when the minimua degree strategy is adopted. A vector that contains the nmaber of predecessors for each node in tbe path graph is used as a second criterion, yielding a local minimization of tbe number of non-zero elements in uri or, equivalently, of the mean path length. A way to compute " this vector which requires a more complex logic than other simpler methods is suggested. However, the promising results obtained with the test networks (above a 35% saving in operations count w.r.t. minimum degree) justify its use. Further work is necessary to better understand how local minimum fill-in strategies interact with local minimum path length strategies in a global sense. Vhile einieum fill-in strategies (like KD) may eventually lead to satisfactory results fro. the point of view of path length, the opposite 1s not true. Using HNP as the main criterion gives an excessive number of fill-ins which, in turn, produce longer paths. This is why KNP is only used as a tie-break criterion. Is it possible, however, that other combinations of MD and HNP strategies lead to better results7 Some data are presented in the paper which suggest that the answer is affirlll8tive. RBPBRBNCBS • (11 -Tinney V.F., lIalker J.V.~ Direct Solutions of Sparse Network Equations by Optimally Ordered Triangular Factorization. Procee. IEEE vol. 55 pp. 1801-1809, 1967. [2) -Tinney II.F., Brandwajn V., Chan S.H., Sparse Vector Methods. IEEE Trans. on PAS-I04, pp • 295-301, 1985 • [3) - Chan S.M., Brandwajn V., Partial Hatrix Refactorization. IEEE Trans. on PIIRS-1, pp. 193-200, 1986. [4) -Betancourt R., Alvarado F.L., Inversion of Sparse Matrices. IEEE PIIRS-l, pp. 74-81, 1986. Parallel Trans. on [5) -Brandwajn V., Tinney II.F., Generalized Method of Fault Analysis. IEEE Trans. on PAS-104, pp. 1301-1306, 1985. [6) -Brandwajn V., Efficient Bounding Method for Linear Contingency Analysis. IEEE/PES 1987 Yinter Meeting, New Orleans. 1987. [7] - G6mez A., Franquelo L.G., Node Ordering Algorithms for Sparse Vector Method Improvement. IEEE/PES 1987 Yinter Meeting. [8] - Betancourt R., An Efficient Heuristic Ordering Algorithm for Partial MatriK Refactorization. IEEE/PES 1987 Summer Meeting. [9] - G6mez A., Franquelo L.G., A Node Ordering Algorithm to Speed up the Solution of Sparse Matrix and Sparse Vector Linear Equation Systems. AMSE Int. Conf. Sept. 1986. [10] -Duff 1.5., Erisman A.M., Reid J.K., Direct Methods for Sparse Matrices. OKford University Press, N.Y., 1986, Chapt. VII. APPENDIX: Practical implementation. There may be several alternatives to actually implement both MD and MD-MNP algorithms, depending mainly on the way the graph's structure is stored and dealt with. An iml ementation is proposed here which is not necessarily the most efficient one but it is only intended to show that MD-MNP is not so compleK compared to MD as it seems at first glance. The usual linked data structure is adopted to store, for each node, the set of adjacent nodes. Vector FIRST points to the beginnings of these sets. CREATE is a routine which inserts a pair of symmetric elements into the chain and updates D (degree) provided the elements did not already exist. NEXADJ gives the currently-pointed adjacent node back and updates the pointer (only two statements are required). MINIMUM is a function which computes the minimum degree node according to step 2 in the main text. Following the notation introduced in the paper and assuming all vectors and the data structure are properly initialized, the MD-MNP algorithm might be as follows: BEGIN k-l while (k<BN) do begin i=MINIMUM(f,D,P) f(i)=k F(i)='true' pointl=FIRST(i) while (point1<>0) do begin NEXADJ(point1,n) if (f(n)~O) then begin D(n)=D(n)- l P(n)=p(n)+P(i) point2=pointl while (point2<>0) do begin NEXADJ(point2,m) if (f(m)=O) CREATE(n,m,D) end end else begin if (F(n)='true') then begin F(n)='false' point2=FIRST(n) while (point2<>0) do begin NEXADJ(point2,m) if (f(m)=O) P(m)=P(m)-P(n) end end end end k=k+1 end END $ * * * * * * * * * * * * * * * Note that step 4 has been embedded into step 5 in order to avoid duplicated accesses to the structure. By omitting P in the line marked with '$' and all of the lines marked with' *' the MD algori thm is obtained. Since the MD algorithm is very well known, its computational compleKity is not going to be discussed here [10). Rather it will serve as a reference to compare the proposed method. Each time a tie appears in the searching of the minimum degree node an additional comparison is required to break it. The resultant number of comparisons is unknown "a priori" but they are peculiar (inherent) to any method which eKploits a second criterion. The other major difference appears in the logic that updates vectors F (frontier) and P (predecessors). Every node becomes a bordering node when it is eliminated. Later, it leaves forever the boundary when any of its adjacent nodes is eliminated. Hence, at the end of the ordering process the condition F(n)='true' has been realised N-l times, once for each node (eKcept the last one). This means that only one extra swept of the graph's overall structure is required, compared to MD. In addition, 2b updatings of F and P are carried out, where b is the number of nonzero elements in U. It is clear from the above paragraph that the overhead introduced is not very significant. Furthermore, since the proposed method gives usually less fill-in, the resultant time is even better than was eKpected, mainly because CREATE, which has an involved logic, is called fewer times. Other refined versions commented in the paper maybe, however, more time-consuming. Due to space limitations they will not be analyzed here. ACKNOYLEDGEKENTS. The authors acknowledge support of Spanish Comisi6n Interministerial Tecnologia (PAB6-0233). this work by the de Ciencia y Antonio G6mez Exp6sito was born in Andbjar, Jaen, Spain, on August 26, 1957. He received the Ingeniero Industrial and the Doctor Ingeniero Industrial degrees from the Universidad de Sevilla, Spain, in 1983 and 19B5, respectively. Since 1982 he has been an Assistant and Associated Professor at the Departamento de Ingenieria Electrica in the Escuela Superior de Ingenieros Industriales of the Universidad de Sevilla. His current research interests lie in sparse matrices and reactive power control. Leopoldo Garcia Franquelo was born in MAlaga, Spain, on April 14, 1954. He received the Ingeniero Industrial and the Doctor Ingeniero Industrial degrees from the Universidad de Sevilla, Spain, in 1977 and 1980, respectively. Since 1978 he has been Assistant, Associated and Professor at the Departamento de Ingenieria Electr6nica, de Sistemas y AutomAtica in the Escuela Superior de Ingenieros Industriales of the Universidad de Sevilla. His current interests include mathematical modelling of circuits, computer applications and programming techniques.