潮流不同排序方案的比较文献翻译中英文对照(1)大学论文.doc

外文翻译（原文）
中文4900字
A Comparison of Power Flow by Different Ordering Schemes

Abstract—Node ordering algorithms, aiming at keeping sparsity as far as possible, are widely used today. In such algorithms, their influence on the accuracy of the solution is neglected because it won’t make significant difference in normal systems. While, along with the development of modern power systems, the problem will become more ill-conditioned and it is necessary to take the accuracy into count during node ordering. In this paper we intend to lay groundwork for the more rationality ordering algorithm which could make reasonable compromising between memory and accuracy. Three schemes of node ordering for different purpose are proposed to compare the performance of the power flow calculation and an example of simple six-node network is discussed detailed.
Keywords—power flow calculation; node ordering; sparsity; accuracy; Newton-Raphson method ; linear equations
I. INTRODUCTION
Power flow is the most basic and important concept in power system analysis and power flow calculation is the basis of power system planning, operation, scheduling and control [1].Mathematically speaking, power flow problem is to find a numerical solution of nonlinear equations. Newton method is the most commonly used to solve the problem and it involves repeated direct solutions of a system of linear equations. The solving efficiency and precision of the linear equations directly influences the performance of Newton-Raphson power flow algorithm. Based on numerical mathematics and physical characteristics of power system in power flow calculation, scholars dedicated to the research to improve the computational efficiency of linear equations by reordering nodes’ number and received a lot of success which laid a solid foundation for power system analysis.
Jacobian matrix in power flow calculation, similar with the admittance matrix, has symmetrical structure and a high degree of sparsity. During the factorization procedure, nonzero entries can be generated in memory positions that correspond to zero entries in the starting Jacobian matrix. This action is referred to as fill-in. If the programming terms is used which processed and stores only nonzero terms, the reduction of fill-in reflects a great reduction of memory requirement and the number of operations needed to perform the factorization. So many extensive studies have been concerned with the minimization of the fill-ins. While it is hard to find efficient algorithm for determining the absolute optimal order, several effective strategies for determining near-optimal orders have been devised for actual applications [2, 3]. Each of the strategies is a trade-off between results and speed of execution and they have been adopted by much of industry. The sparsity-programmed ordered elimination mentioned above, which is a breakthrough in power system network computation, dramatically improving the computing speed and storage requirements of Newton’s method [4].
After sparse matrix methods, sparse vector methods [5], which extend sparsity exploitation to vectors, are useful for solving linear equations when the right-hand-side vector is sparse or a small number of elements in the unknown vector are wanted. To make full use of sparse vector methods advantage, it is necessary to enhance the sparsity of L-1by ordering nodes. This is equivalent to decreasing the length of the paths, but it might cause more fill-ins, greater complexity and expense. Countering this problem, several node ordering algorithms [6, 7] were proposed to enhance sparse vector methods by minimizing the length of the paths while preserving the sparsity of the matrix.
Up to now, on the basis of the assumption that an arbitrary order of nodes does not adversely affect numerical accuracy, most node ordering algorithms take solving linear equations in a single iteration as research subject, aiming at the reduction of memory requirements and computing operations. Many matrices with a strong diagonal in network problems fulfill the above assumption, and ordering to conserve sparsity increased the accuracy of the solution. Nevertheless, if there are junctions of very high and low series impedances, long EHV lines, series and shunt compensation in the model of power flow problem, diagonal dominance will be weaken [8] and the assumption may not be tenable invariably. Furthermore, along with the development of modern power systems, various new models with parameters under various orders of magnitude appear in the model of power flow. The promotion of distributed generation also encourage us to regard the distribution networks and transmission systems as a whole in power flow calculation, and it will cause more serious numerical problem. All those things mentioned above will turn the problem into ill-condition. So it is necessary to discuss the effect of the node numbering to the accuracy of the solution.
Based on the existing node ordering algorithm mentioned above, this paper focus attention on the contradiction between memory and accuracy during node ordering, research how could node ordering algorithm affect the performance of power flow calculation, expecting to lay groundwork for the more rationality ordering algorithm. This paper is arranged as follows. The contradiction between memory and accuracy in node ordering algorithm is introduced in section II. Next a simple DC power flow is showed to illustrate that node ordering could affect the accuracy of the solution in section III. Then, taking a 6-node network as an example, the effect of node ordering on the performance of power flow is analyzed detailed in section IV. Conclusion is given in section VI.
II. CONTRADICTION BETWEEN MEMORY AND ACCURACY
IN NODE ORDERING ALGORITHM
According to numerical mathematics, complete pivoting is numerically preferable to partial pivoting for systems of liner algebraic equations by Gaussian Elimination Method (GEM). Many mathematical papers [9-11] focus their attention on the discrimination between complete pivoting and partial pivoting in (GEM). Reference [9] shows how partial pivoting and complete pivoting affect the sensitivity of the LU factorization. Reference [10] proposes an effective and inexpensive test to recognize numerical difficulties during partial pivoting requires. Once the assessment criterion can not be met, complete pivoting will be adopted to get better numerical stability. In power flow calculations, partial pivoting is realized automatically without any row-interchanges and column-interchanges because of the diagonally dominant features of the Jacobin matrix, which could guarantee numerical stability in floating point computation in most cases. While due to rounding errors, the partial pivoting does not provide the solution accurate enough in some ill-conditionings. If complete pivoting is performed, at each step of the process, the element of largest module is chosen as the pivotal element. It is equivalent to adjust the node ordering in power flow calculation. So the node relate to the element of largest module is tend to arrange in front for the purpose of improving accuracy.
The node reordering algorithms guided by sparse matrix technology have wildly used in power system calculation, aiming at minimizing memory requirement. In these algorithms, the nodes with fewer adjacent nodes tend to be numbered first. The result is that diagonal entries in node admittance matrix tend to be arranged from least to largest according to their module. Analogously, every diagonal submatrices relate to a node tend to be arranged from least to largest according to their determinants. So the results obtained form such algorithms will just deviate form the principle follow which the accuracy of the solution will be enhance. That is what we say there is contradiction between node ordering guided by memory and accuracy.
III. DIFFERENCE PRECISION OF THE SOLUTION USING PARTICAL PIVOTING AND COMPLETE PIVOTING
It is said that complete pivoting is numerically preferable to partial pivoting for solving systems of linear algebraic equations. When the system coefficients are varying widely, the accuracy of the solution would be affect by rounding errors hardly and it is necessary to take the influence of the ordering on the accuracy of the solution into consideration.

Fig.1 DC model of Sample 4-node network
As an example, consider the DC model of sample 4-node system shown in Figure 1. Node 1 is the swing node having known voltage angle; nodes 2-4 are load nodes. Following the original node number, the DC power flow equation is:

To simulate computer numerical calculation operations, four significant figures will be used to solve the problem. Executing GEM without pivoting on (1) yields the solution[ θ2,θ3,θ4]T=[-0.3036,-0.3239,-0.3249]T, whose components differ from that of the exact solution [θ2, θ3,θ4]T=[-0.3,-0.32,-0.321]T. A more exact solution could be obtained by complete pivoting: [θ2,θ3, θ4]T=[-0.3007,-0.3207,-0.3217]T, and the order of the node after row and column interchanges is 3,2,4. So this is a more reasonable ordering scheme for the purpose of getting more high accuracy.
IV. THE INFLUENCE OF NODE REODERING ON THE PERFORMANCE OF NEWTON-RAPHSON POWER FLOW METHOD

Fig.2 Sample 6-node network
On the basis of the above-mentioned analysis, the scheme for node reordering will not only affect memory requirement but also the accuracy of the solution in solving linear simultaneous equations So performance of Newton-Raphson power flow method will be different with various node ordering. In this section three schemes of ordering for different purpose will be applied to a sample 6-node network shown in Fig 2 to compare the influence of them on the accuracy of the solution, the convergence rate, the calculated amount and the memory needed in power flow computation. The detail of the performance is shown in table IV.
A. Puropse 1 Saving Memory as far as possible
At present, there are various schemes widely used for node numbering in near-optimal order to reduce fill-ins and save memory. The only information needed by the schemes is a table describing the node-branch connection pattern of the networks. An order that would be optimal for the reduction of the admittance matrix of the network is also optimal for the table of factors related Jacobian matrix. Different schemes reach different compromise between programming complexity and optimality. In this paper, what we concern about is how the result of the numbering affects the computational performance. The programming efficiency is beyond the scope of the present work. To save memory, a dynamic node ordering scheme similar to the third scheme presented in [2] is adopted in this section. Execution steps of the algorithm are as follows.
Scheme I
a) Number the node degree of which is one. If more than one node meet this criterion, number the node with the smallest original number. If there are not sucn nodes any more, start with step b);
b) Number the node so that no equivalent branches will be introduced when this node is eliminated. If more than one node meets this criterion, number the one with the smallest original number. If we can not start with step a) or step b), turn to step c);
c) Number the node so that the fewest branches will be introduced when this node is eliminated. If not only node could introduce fewest branches, number the one with the largest degree.
Once certain node is numbered in the step above, update the degree of relevant nodes and topological information. Until all the nodes are numbered, the process of node numbering ends up.
TABLE I. REORDERED NODES USING SCHEME ONE

Following the steps of scheme I, the sequence of the node numbered for the 6-node network is given in table I. No fill-in will be introduced during the procedure of solving the linear equation, so the table of factors and the Jacobian matrix will have completely identical structure. So the memory requirement for the table of factors is 0.256Kb, which is the same with that for the Jacobian matrix. Normally, an acceptable solution can be obtained in four or five iterations by Newton-Raphson method. While, the number of iterations required for this example is thirty-three because of the ill-conditioned caused by the small impedance branch. 123 multiply operations will be performed during forward substitution and backward substitution for each iteration, and 7456 multiply operations will be performed throughout the whole process of solving.
B. Puropse 2: Improving Accuracy Using Complete Pivoting
Considering that complete pivoting is numerically preferable to partial pivoting, in this section complete pivoting is adopted to improve accuracy of the solution of the linear equations, aiming at reducing the number of iterations. Here nodes relate to large determinant of the diagonal submatrices intend to be arrange in front. To some extern, the modulus of the entries on the main diagonal of the admittance matrix could indicate the magnitude of the determinant of the submatrices on the main diagonal of the Jacobian matrix. For convenience, we make use of admittance matrix to determine the order of numbers.
Scheme II
a) Form the nodal admittance matrix;
b) Factorize the nodal admittance matrix with complete pivoting. Record the changes on the position of the nodes;
c) Determine the new number of the node according to the positong of node in the end of the factorization;
TABLE II. REORDERED NODES USING SCHEME TWO

Executing scheme II, complete pivoting might automatic performed without row and column exchanges. The module of entries on main diagonal corresponding to such node may become larger by summing more branch parameter, as a result, the nodes, degree of which is larger, tend to be numbered first. So the results of such scheme may depart form the principle of node numbering guided by sparse matrix methods and many fill-ins might be introduced. The sequence of the node numbered for 6-node network is list in table II. Six fill-ins will be produced, so more memory (0.488Kb) and more operations (321 multiply operations) are spent in the procedure of forward and backward substitution during once iteration. The total number of iterations required reduces to thirteen, which suggests that the calculation accuracy for linear equations could be raised by complete pivoting. Finally, the number of multiply operations reduces to 5573 thanks to smaller number of iterations.
C. Puropse 3: Improving Accuracy while preserving the sparsity
Only one small impedance branch exists in the system, so only four entries (submatrices) corresponding to node 4 and node 6 are very large in admittance matrix (Jacobin matrix). During the process of forward substitution, once node 4 or node 6 is elimination, the submatrix co