IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 23, NO. 4, NOVEMBER 2008 1727Multifrontal Solver for Online PowerSystem Time-Domain SimulationSiddhartha Kumar Khaitan, James D. McCalley, Fellow, IEEE, and Qiming Chen, Member, IEEEAbstract—This paper proposes the application of unsymmetricmultifrontal method to solve the differential algebraic equations(DAE) encountered in the power system dynamic simulation. Theproposed method achieves great computational efficiency as com-pared to the conventional Gaussian elimination methods and otherlinear sparse solvers due to the inherent parallel hierarchy presentin the multifrontal methods. Multifrontal methods transform orreorganize the task of factorizing a large sparse matrix into a se-quence of partial factorization of smaller dense frontal matriceswhich utilize the efficient Basic Linear Algebra Subprograms 3(BLAS 3) for dense matrix kernels. The proposed method is com-pared with the full Gaussian elimination methods and other directsparse solvers on test systems and the results are reported.Index Terms—Differential algebraic equations, dynamic simula-tion, frontal methods, linear solvers, multifrontal methods, UMF-PACK.I. INTRODUCTIONSIMULATION tools are an integral part in the design andoperation of large interconnected power systems. The pur-pose of simulation is monitoring and tracking, and devisingpreventive or corrective action strategies for mitigating the fre-quency and impact of high consequence events. Dynamic sim-ulation of power systems is important for secure power gridexpansion, and it significantly impacts future design and op-eration of large interconnected power systems. The differen-tial algebraic equations (DAEs) for the dynamic simulation aresolved to get the transient response of the power system. Thepower system typically has thousands of components includinggenerators and associated controls, loads, transformers, lines,and voltage control elements. Detailed modeling of the powersystem results in thousands of differential and algebraic equa-tions forming the DAE.There are two broad categories of numerical integrationmethods: explicit and implicit. Iterative methods like theNewton method are needed to solve the implicit nonlinearequations resulting from implicit numerical methods. The mostattractive feature of implicit methods is that they allow veryManuscript received December 28, 2007; revised May 13, 2008. Current ver-sion published October 22, 2008. This work was supported in part by PSercProject S26 Risk of Cascading outages and in part by the U.S. Departmentof Energy Consortium for Electric Reliability Technology Solutions (CERTS).Paper no. TPWRS-00960-2007.S. K. Khaitan and J. D. McCalley are with the Department of Electrical andComputer Engineering, Iowa State University, Iowa, IA 50010 USA (e-mail:[email protected]; [email protected]).Q. Chen is with Macquarie Cook Power, Inc., Houston, TX 77002 USA(e-mail: [email protected]).Color versions of one or more of the figures in this paper are available onlineat http://ieeexplore.ieee.org.Digital Object Identifier 10.1109/TPWRS.2008.2004828large time steps. Reference [1] reports the usage of 10-s timesteps in EUROSTAG and [2] reports the usage of 20-s timesteps in EXSTAB without losing numerical stability.In the literature for the solution of dynamic algebraic equa-tions, [3], there has been a significant effort to develop A-stable,accurate and fast numerical integration methods with variabletime steps. Reference [1] developed a mixed Adams-BDF al-gorithm with variable step size and variable integration order toreliably discriminate between stable and unstable phenomenaand efficiently tackle large stiff power system models. Ref-erence [2] developed a variable time step implicit integrationscheme based on a modified Trapezoidal method for extendedterm time-domain simulation of power systems. In reference[4], a new decoupled time-domain simulation algorithm isproposed that takes advantage of both explicit and implicitmethods. It is based on decoupling the system into stiff andnon-stiff parts via invariant subspace decomposition and usingthe implicit method for the stiff part and explicit method forthe non-stiff part to gain computationally efficiency. All theseapproaches have focused on integration algorithm developmentto gain efficiency. Although the various numerical integrationschemes differ in their convergence, order, stability, and otherproperties, they do not necessarily offer considerable improve-ment in computational gain. However, the core of the resultingnonlinear equations from any of the integration schemes is thesolution of a sparse linear system, which is the most computa-tionally intensive part of a DAE solver. This is exploited in thework described here, via implementation of the unsymmetricmultifrontal algorithms for sparse linear systems, which, whencombined with a robust integration scheme, achieve very fasttime-domain simulation.Section II provides background of the numerical methodsused, namely, the integration scheme, the solution of non-linear equations and the linear solvers. Section III introducesfrontal methods, useful because they provide foundations onwhich multifrontal methods are based. Section IV describesfundamentals of multifrontal solvers and uses some simpleexamples to illustrate. Section V compares simulation resultsof a power system simulator deploying multifrontal solverswith the same simulator deploying other direct sparse solversand the Gaussian elimination solver, using two test systems.Section VI presents a discussion and Section VII concludes.II. NUMERICAL METHODSMost current methods for performing power system dynamicsimulation are developed for use on conventional sequential ma-chines. This leads to the natural conclusion that there are two0885-8950/$25.00 © 2008 IEEEAuthorized licensed use limited to: Iowa State University. Downloaded on September 9, 2009 at 14:37 from IEEE Xplore. Restrictions apply.1728 IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 23, NO. 4, NOVEMBER 2008viable options to reduce the wall-clock time to solve a computa-tionally intensive problem like power system time-domain sim-ulation. These are 1) advanced hardware technology in terms ofspeed, memory, I/O, and architecture, and 2) a more efficient al-gorithm. Although the emphasis is generally on the hardware,nevertheless efficient algorithms can offer great advantage inachieving the desired speed. There exists a symbiotic relation-ship between the