Numerical Methods For On-line Power System Load flow Analysis
Energy Syst (2010) 1: 273–289DOI 10.1007/s12667-010-0013-6O R I G I N A L PA P E RNumerical methods for on-line power system load flowanalysisSiddhartha Kumar Khaitan · James D. McCalley ·Mandhapati RajuReceived: 4 February 2010 / Accepted: 20 April 2010 / Published online: 6 May 2010 Springer-Verlag 2010Abstract Newton-Raphson method is the most widely accepted load flow solutionalgorithm. However LU factorization remains a computationally challenging task tomeet the real-time needs of the power system. This paper proposes the application ofvery fast multifrontal direct linear solvers for solving the linear system sub-problemof power system real-time load flow analysis by utilizing the state-of-the-art algorithms for ordering and preprocessing. Additionally the unsymmetric multifrontalmethod for LU factorization and highly optimized Intel Math Kernel Library BLAShas been used. Two state-of-the-art multifrontal algorithms for unsymmetric matricesnamely UMFPACK V5.2.0 and sequential MUMPS 4.8.3 (“Multifrontal MassivelyParallel Solver”) are customized for the AC power system Newton-Raphson basedload flow analysis. The multifrontal solvers are compared against the state-of-the-artsparse Gaussian Elimination based HSL sparse solver MA48. This study evaluatesthe performance of above multifrontal solvers in terms of number of factors, computational time, number of floating-point operations and memory, in the context of loadflow solution on nine systems including very large real power systems. The results ofthe performance evaluation are reported. The proposed method achieves significantreduction in computational time.This work was supported in part by U.S. Department of Energy Consortium for Electric ReliabilityTechnology Solutions (CERTS).S.K. Khaitan ( ) · J.D. McCalleyDepartment of Electrical and Computer Engineering, Iowa State University, Iowa, IA 50011, USAe-mail: skhaitan@iastate.eduJ.D. McCalleye-mail: jdm@iastate.eduM. RajuOptimal Inc., Plymouth, MI 48312, USAe-mail: raju192@gmail.com
274S.K. Khaitan et al.Keywords Load flow analysis · Linear solvers · Multifrontal methods · MUMPS ·UMFPACK · MA481 IntroductionLoad flow solutions are among the most frequently performed power network calculations for steady state operating conditions of the power system. In the operationalcontext, for the load flow simulations to be of prime value to the operators, it mustbe performed in a very computationally efficient manner. Over the past few decadesseveral methods have been developed to perform load flow simulations in a reliable,versatile and computationally efficient manner with optimal storage requirements [1,38–42]. However the Newton-Raphson (NR) methods are the most widely acceptedsolution methods due to their robustness and fast (quadratic) convergence characteristics. The core of the iterative NR method is the solution of a system of linearequations which accounts for almost 90% of the solution time. Solving the linear system sub-problem of the NR method involves a computationally challenging task ofLU factorization at every iteration. Sparse Gaussian elimination and matrix inversiontechniques have been used to reduce computational burden. Any further reduction ofcomputational time is advantageous for a heavily used tool, like load flow simulationstudies, as it allows the power engineers and operators to perform more simulationsfor different scenarios. Fast decoupled methods have been developed for real-timeload flow solutions. They require a single simpler LU factorization followed by forward elimination and backward substitution on a much smaller matrix for successiveiterations. However the fast decoupled methods fail to converge for systems understressed operation conditions and/or with high R/X ratios, and one has to resort tofull NR load flow simulations. To reduce the computational burden and the wall clocktime, for the load flow solution, multifrontal methods [2] have been proposed in thispaper.On the windows platforms, the multifrontal methods were used almost a decadeago for power flow in reference [3] which implements UMFPACK V2 [4] with default ordering. No information is provided regarding BLAS (Basic Linear AlgebraSubprograms) which provides standard building blocks for performing basic vectorand matrix operations. The focus of this paper was to promote automatic code differentiation in power flow algorithms and it was stated that the resulting code wasslower than conventional packages with hand coded Jacobian. Since then, there hasbeen a lot of advancement in the area of multifrontal methods (including algorithmicimprovements in UMFPACK [4–9]) to make them highly computationally efficient.Currently, there is an abundance of advanced algorithms for ordering schemes toreduce fill-in, for post-ordering and restructuring of elimination trees. Efficient andoptimized elimination trees, preordering strategies, reduced working storage and reduction in indirect memory access give higher speed and performance [10–12].Reference [13] proposes FPGA hardware technology for the solution of sparseequations and compares the result for the solution phase alone with multifrontalmethods on a Linux platform. The ordering was done using MATLAB functions. Reference [14] uses MUMPS, a parallel multifrontal solver [15–21], on a Linux platform
Numerical methods for on-line power system load flow analysis275for symmetric indefinite matrices that arises in the solution of security constrainedAC-OPF problem. We are not aware of any other multifrontal implementations for thepower system AC load flow solutions with unsymmetric Jacobian matrices. Specifically there is no instance, in the open literature, of the application of MUMPS for thepower flow solution with unsymmetrical Jacobian matrices.The objective of this paper is to aid in security assessment through enhancedcomputational speed for the solution of the linear system of equations that arisein the NR solution of the power system load flow. To achieve the desired computational speed for load flow solution, this paper implements sparse direct solversbased on unsymmetric multifrontal methods MUMPS [15–21] and UMFPACK [4–9].Both MUMPS and UMFPACK are available free in the public domain. MUMPSallows for external interface of other up-to-date sequential ordering softwares likeMETIS [22], PORD [23] and SCOTCH [24] and several internal orderings likeAMD [25], QAMD [26], and AMF [26] whereas in UMFPACK the preferred ordering for unsymmetrical matrices is COLAMD [4–9]. In this study except SCOTCHall other orderings have been interfaced with MUMPS and their performances areevaluated in terms of number of entries in the factors, computational time, numberof floating-point operations and memory, and the results are reported. Highly optimized Intel Math Kernel Library BLAS are used which are very critical for performance [27]. The results are compared against the state-of-the-art sparse Gaussianelimination solver MA 48 [28, 29], available free to the researchers. This study isthe first of its kinds in implementing latest unsymmetrical multifrontal solvers withdifferent choice of ordering schemes, highly optimized BLAS and intelligent choiceof different phases within a sparse solver to save computational time to allow forreal-time security assessment.Section 2 provides a brief background on the numerical formulation of the loadflow problem, the solution of non linear equations and the linear solvers. Section 3presents an overview of multifrontal solvers MUMPS [15–21] and UMFPACK [4–9]proposed in this paper for linear system sub-problem of the NR load flow solution.Section 4 discusses the implementations issues regarding the solvers. Section 5 contains the results and the discussion and Sect. 6 concludes.2 Numerical methodsEfficient algorithms and hardware together or independently can offer great advantage in achieving the desired speed for real-time operations and security assessment.In this paper, we focus on algorithmic improvements to achieve high computationalgain for full NR load flow solutions.We divide our load flow software into three parts, namely (1) Preprocessor(2) Newton-Raphson solver and (3) the output assembler. Preprocessor includes theuser interface, assembling the admittance matrix and the Jacobian building. Our studies indicate about 90–95% of the computational time is spent on the NR solver. TheNR solver involves numerical analysis techniques which are broadly classified intotwo categories namely (1) solution of nonlinear equations and (2) the solution oflinear equations.
276S.K. Khaitan et al.2.1 Non linear equation solutionThe developed equations have the same notations as in [1]. Consider the set of equations belowy1 f1 (x1 , x2 , x3 , . . . , xn )y2 f2 (x1 , x2 , x3 , . . . , xn ).(1)yn fn (x1 , x2 , x3 , . . . , xn )Expanding the first equation about the initial solution [x1 (0), x2 (0), . . . , xn (0)],we get: f1 y f1 [x1 (0), x2 (0), . . . , xn (0)] [x1 x1 (0)] x1 x1 x1 (0) f1 f1 [x x(0)]··· [xn xn (0)](2)11 x2 x2 x2 (0) xn xn xn (0)after expanding other equations similarly and expressing in the matrix form we get: f f1 f1 1. x2 xnx1 x1 (0)f1 [x1 (0), x2 (0), . . . , xn (0)]y11 x y2 f2 [x1 (0), x2 (0), . . . , xn (0)] f2 f2 . . . f2 x2 x2 (0) x1 x2 xn . . . . . . fn fn fn x(0)ynfn [x1 (0), x2 (0), . . . , xn (0)]xnn. . . xn x1 x2(3)Equation (3) can be expressed in compact form asy f [x(0)] J (0)[x x(0)](4)x x(0) J (0) 1 [y f {x(0)}](5)whereIn recursive form using iteration count i, the above equation becomesxi 1 xi Ji 1 [y f (xi )](6)This the Newton-Raphson solution formulation.2.2 Problem formulationThe fundamental bus bar equations at node k are given below:nIk Ykj Vjj 1(7)
Numerical methods for on-line power system load flow analysisSk Vk Ik277(8)where Ik is the injected current at node k, Vk is the voltage at node k, Ykj is theadmittance between node k and j and Sk is the complex power. Substituting (7)in (8), the complex power can be written asSk f (Vk )(9)Equation (9) has the same form as (1) and thus can be solved using the NewtonRaphson method. The set of nonlinear algebraic equations in (9) are solved at eachiteration using the Newton-Raphson method, and the unknowns are updated as in (6).In short form (3) is written as PJ1 J 2 V /V (10) Q θJ3 J4where V and are the correction variables for voltage magnitude and voltagephase angle. The Newton iterations terminate when the largest absolute mismatchvector is less than a pre-specified tolerance. Computation of the correction vector[ V , ]T requires the solution of the set of linear equations given by (10) whichis discussed in the next section.2.3 Linear solverThe most computationally intensive step in the solution of the load flow is the solution of the sparse system of linear equations. For the above power system loadflow problem formulation, the Jacobian matrix J is highly sparse, has good structuralsymmetry but is poor in numerical symmetry. We use this fact to gain computationalefficiency for real-time load flow and security assessment by employing multifrontalbased sparse linear solvers with optimized BLAS library and effective ordering strategies to reduce fill-in.A typical sparse solver consists of four distinct phases in the solution of linearsystem:1. The preprocessing and the ordering step which minimizes the fill-in and exploitsspecial structures such as block triangular form.2. The symbolic factorization step determines the nonzero structures of the factors Land U , sets up the data structures for storing nonzeros of L and U and allocatesmemory for the nonzeros.3. The numerical factorization step involves inputting the numerical values, computing L and U via intelligent factorization on multiple small, but dense “fronts orfrontal matrix”, with pivoting to maintain numerical stability.4. The solve step performs forward and/or backward substitutions and eliminationsto solve linear system.All these steps can be called separately or as a combination of each other. This canbe exploited to save computational effort during the solution of subsequent iterations
278S.K. Khaitan et al.in the solution of a set of linear equations. For example if the structure of the matrixdoes not change during every iteration, the analysis step can be skipped after evaluating once. Similarly, if the left hand matrix does not change, both the analysis andthe factorization steps can be skipped. The first three steps are most time consumingand an effective strategy is incorporated to intelligently select required steps duringiterations. This results in significant computational saving and is discussed in Sect. 5towards the end.In the following sections we give a brief overview of the two multifrontal solversand the different ordering schemes.3 Multifrontal methodsThe multifrontal method, a generalization of the frontal method, was originally developed for symmetric systems [19]. Subsequently, an unsymmetric multifrontal algorithm [5] was developed for general sparse unsymmetric matrices. An overviewon the theory and mathematical foundation of multifrontal methods is given in [2]and [30]. Multifrontal methods reorganize the task of factorizing a large sparse matrix into a sequence of partial factorization of smaller dense frontal matrices andmakes full use of the high performance computer architecture by invoking the level3 Basic Linear Algebra Subprograms (BLAS) library. Thus memory requirement isheavily reduced, and computing speed is greatly enhanced.In the present study, MUMPS 4.8.3 and UMFPACK V5.2.0 are used as the multifrontal engine for the solution of (10).3.1 MUMPSMUMPS 4.8.3 (“Multifrontal Massively Parallel Solver”) written in Fortran 90, is apackage, based on multifrontal algorithms, for solving systems of linear equationsof the form in (10), where J is a square sparse matrix that can be either unsymmetric, symmetric positive definite, or general symmetric. It performs a direct factorization A LU or A LDLT depending on the symmetry of the matrix. MUMPSis primarily a parallel distributed solver designed for computational efficiency andexploits both parallelism arising from sparsity in the matrix A and from dense factorizations kernels. However the analysis phase is sequential. The parallel versionof MUMPS requires MPI [31] for message passing and makes use of the BLAS,BLACS, and ScaLAPACK [32] libraries. The sequential version only relies on BLAS.The MUMPS solver facilitates error analysis, iterative refinement, scaling of the original matrix, out-of-core capability, detection of null pivots, basic estimate of rank deficiency and null space basis, and computation of a Schur complement matrix alongwith the factorization. MUMPS has several built-in ordering algorithms, and providesa tight interface to external ordering packages such as PORD, SCOTCH or METISand also a possibility for the user to input a given ordering. PORD is provided as apart of the MUMPS package. METIS and SCOTCH need to be separately linked tothe MUMPS solver.
Numerical methods for on-line power system load flow analysis2793.1.1 BLASThe BLAS (Basic Linear Algebra Subprograms) provide standard building blocks forperforming basic vector and matrix operations. The Level 1 BLAS performs scalar,vector and vector-vector operations, Level 2 BLAS performs matrix-vector operations, and the Level 3 BLAS performs matrix-matrix operations. The BLAS are efficient, portable, and widely available, and they are commonly used in the developmentof high quality linear algebra software. ATLAS, ACML and Intel Math Kernel Library BLAS are examples of BLAS libraries.3.1.2 Ordering methodsA fill-reducing ordering is crucial for efficient numerical solution of sparse linear systems. The goal of the preordering is to find a permutation matrix P so that the subsequent factorization has the minimum fill-in. However, this problem is NP-complete,so heuristics are used. Over the years two main classes of heuristics have evolvednamely (a) minimum-degree (MD)-based heuristics, and (b) graph-partitioning (GP)based heuristics. MD-based heuristics are local greedy heuristics that reorder thecolumns of a sparse matrix such that the column with the fewest non-zeros at a givenstage of factorization is the next one to be eliminated at that stage.The minimum degree ordering algorithm produces factors with relatively low fillin on a wide range of matrices. Because of this, the algorithm has received muchattention and research over the past three decades to improve their run time and quality. The multiple minimum-degree (MMD) algorithm and the approximate minimumdegree (AMD) represent the state of the art in MD based heuristics.GP-based heuristics regard the sparse matrix as the adjacency matrix of a graphand follow a divide-and-conquer strategy to label the nodes of the graph by partitioning it into smaller subgraphs.Nested Dissection is one more effective method of finding an elimination ordering.The algorithm uses a divide and conquer strategy on the graph. Removal of a setof vertices results in two new graphs on which this dissection may be performedseparately. The results for the two parts may then be combined to find the solution ofthe entire graph.A new class of hybrid ordering packages, that combines the above two algorithmsto produce better and robust ordering, has been developed in the recent past. The hybrid orderings are sometimes called incomplete nested dissection. Those algorithmscombine top-down multilevel nested dissection algorithms with bottom-up minimumdegree (AMD or MMD) or minimum fill (MMF) local heuristics. A more generalclassification of hybrid schemes is known as multi-section ordering. PORD (Paderborn Ordering tool) uses the multi-section ordering.MUMPS has in-built approximate minimum degree ordering algorithm AMD,AMF (approximate minimum fill algorithm), a nested dissection (ND) or a externally computed given ordering. MUMPS also provides for external interfacing ofSCOTCH, PORD and METIS. SCOTCH is a hybrid of nested dissection and AMD.PORD implements a tighter coupling between nested dissection and approximateminimum fill, whereas METIS uses multilevel nested dissection and minimum degree. The degree of coupling depends on the partitioner. AMF, SCOTCH and PORD
280S.K. Khaitan et al.have been tightly coupled in the sense that the assembly tree is obtained as an outputof the partitioner. In the case of METIS only ordering is obtained. It is thus said to beloosely coupled.3.2 UMFPACKUMFPACK consists of a set of ANSI/ISO C routines for solving unsymmetric sparselinear systems using the unsymmetric multifrontal method. It requires the matrixto be input in a sparse triplet (compressed sparse column) format. More detaileddiscussion on the solver can be found in [4–9]. UMFPACK has the option to useBLAS for high performance. For general unsymmetrical matrices, the multifrontalmethod offers a significant performance advantage over more conventional factorization schemes [33].4 ImplementationOur simulator is written in C . The MUMPS solver is a set of Fortran 90 routines,whereas the UMFPACK solver is a set of ANSI/ISO C routines and MA48 is a set ofFortran 77 routines. Regarding the implementation, because of the language differences, proper interface driver routines were written and libraries were developed bothfor the solvers and the ordering algorithms (METIS and PORD). MUMPS is writtenprimarily as a parallel solver for Linux architecture and MUMPS is not distributedfor windows architecture. Significant effort was spent on building sequential librariesfor the windows architecture on which our current simulator is developed. SimilarlyMETIS source code along with the makefile is distributed for building libraries onLinux. Only binaries are
Numerical methods for on-line power system load flow analysis 277 S k V k Ik (8) where Ik is the injected current at node k, Vk is the voltage at node k, Ykj is the admittance between node k and j and Sk is the complex power. Substituting (7) in (8), the complex power can be written as
Bruksanvisning för bilstereo . Bruksanvisning for bilstereo . Instrukcja obsługi samochodowego odtwarzacza stereo . Operating Instructions for Car Stereo . 610-104 . SV . Bruksanvisning i original
10 tips och tricks för att lyckas med ert sap-projekt 20 SAPSANYTT 2/2015 De flesta projektledare känner säkert till Cobb’s paradox. Martin Cobb verkade som CIO för sekretariatet för Treasury Board of Canada 1995 då han ställde frågan
service i Norge och Finland drivs inom ramen för ett enskilt företag (NRK. 1 och Yleisradio), fin ns det i Sverige tre: Ett för tv (Sveriges Television , SVT ), ett för radio (Sveriges Radio , SR ) och ett för utbildnings program (Sveriges Utbildningsradio, UR, vilket till följd av sin begränsade storlek inte återfinns bland de 25 största
Hotell För hotell anges de tre klasserna A/B, C och D. Det betyder att den "normala" standarden C är acceptabel men att motiven för en högre standard är starka. Ljudklass C motsvarar de tidigare normkraven för hotell, ljudklass A/B motsvarar kraven för moderna hotell med hög standard och ljudklass D kan användas vid
LÄS NOGGRANT FÖLJANDE VILLKOR FÖR APPLE DEVELOPER PROGRAM LICENCE . Apple Developer Program License Agreement Syfte Du vill använda Apple-mjukvara (enligt definitionen nedan) för att utveckla en eller flera Applikationer (enligt definitionen nedan) för Apple-märkta produkter. . Applikationer som utvecklas för iOS-produkter, Apple .
numerical solutions. Emphasis will be placed on standing the under basic concepts behind the various numerical methods studied, implementing basic numerical methods using the MATLAB structured programming environment, and utilizing more sophisticated numerical methods provided as built-in
1. To be an advanced level course in numerical methods and their applications; 2. To (introduce and) develop confidence in MATLAB (and UNIX); 3. To teach mathematical methods through computation; 4. To develop numerical methods in the context of case studies. Objectives 1. To learn numerical methods for data analysis, optimisation,linear .
och krav. Maskinerna skriver ut upp till fyra tum breda etiketter med direkt termoteknik och termotransferteknik och är lämpliga för en lång rad användningsområden på vertikala marknader. TD-seriens professionella etikettskrivare för . skrivbordet. Brothers nya avancerade 4-tums etikettskrivare för skrivbordet är effektiva och enkla att
