## Parallel State Estimation

State estimator is an essential tool for power grid operation. It estimates the states of a power system by fitting the system model to a set of real-time measurement data from remote terminal units through the supervisory control and data acquisition (SCADA) system. By performing weighted-least-squares state estimation (WLS-SE), the resulting states are an optimal fit with improved accuracy compared with the raw measurements. State estimation provides the current power grid status and drives other key energy management system (EMS) functions such as contingency analysis, optimal power flow, economic dispatch, and automatic generation control. The WLS-SE algorithm is an iterative Newton Raphson process, and requires solving a large and sparse linear system during each iteration. This is the most time-consuming part of the state estimation process. In today’s practice, the most common time interval to run the state estimator is 30 to 90 seconds. Today’s commercial EMS tool cannot perform state estimation at the SCADA scan rate of between 2 and 4 seconds. As a result, the system status presented to operators is a past status, which could potentially cause reliability problems. With the help of suitable algorithms and high performance computing techniques, state estimation can be solved at the SCADA rate or faster, which allows operators to know system status much faster compared against today’s practice.

Figure 1. Parallel PCG compared to MTSuperLU on the SGI Altix 3000: execution time of one iteration in seconds in relationship to the number of processors for a 1177-bus system. Click for a larger image.

At Pacific Northwest National Laboratory, we have studied and implemented different algorithms to parallelize and speed up state estimation on both the shared memory and distributed memory architectures, including parallel preconditioned conjugate gradient (PCG) based iterative method algorithms and orthogonal decomposition-based direct method algorithms. For example, Figure 1 shows the comparison results between a multithreaded version of SuperLU 3.0 and parallel PCG with Jacobian preconditioner on SGI Altix 3000 (a shared memory computer) for a 1177-bus system in one iteration of the Newton-Raphson procedure. This result shows that parallel CG method is better in both scalability and absolute execution time.

To further reduce the overall computational time, a cluster-based PCG algorithm has been implemented on a cluster-based NWICEB machine using the Hypre library package. The results of different preconditioners are shown in Figure 2, where the Western Electricity Coordinating Council (WECC) 14,084-bus system is studied. As can be seen, with Eulicd and ParaSails preconditioners, less than 5-second solution time can be achieved for the full state estimation problem of the WECC 14,084-bus system, which is comparable with today’s SCADA cycles.

Figure 2. PCG execution time comparison with different preconditioners on the NWICEB for the WECC 14084-bus system (first iteration). Click for a larger image.

PNNL has tested the PCG method with a ParaSails preconditioner and QR orthogonal decomposition-based approaches using real-world data with weighting measurement equations incorporated. It has been found that while the PCG algorithm can solve the SE problem faster with the help of parallel computing techniques, it might not be good for real-world data because of the large condition number of its gain matrix introduced by the wide range of measurement weights. On the other hand, with the help of the PETSc package, the orthogonal decomposition-based SE algorithm can achieve between 5 and 20 times speedup compared to the commercial EMS tool. Table 1 shows the average computational time for solving the first iteration matrix for the real-world system with 7,500 buses and 9,300 branches on the PNNL Institutional Computing (PIC) Olympus computer, which contains19,200 cores; each core contains a 2.1-GHz AMD Opteron 6272. We expect to see if the parallel state estimation code can run a full-cycle state estimation as fast as the SCADA cycle rate for large systems, which will provide significant help for grid reliability and efficiency.

Table 1. Average computational time for solving the first iteration matrix using PETSc

Case |
# of Rows |
# of Columns |
# of Non-zeros |
Average time(s) |
---|---|---|---|---|

Full |
27.090 | 14.960 | 129.047 | 0.278 |

P-theta |
12.375 | 7.480 | 34.296 | 0.068 |

## Notable Publications

**Papers**

Z. Huang and J. Nieplocha, “Transforming power grid operations via high performance computing,” in Proceeding *IEEE Power Energy Society General Meeting*, 2008.

Y. Chen, Z. Huang, and N. Zhou. 2011. “An advanced framework for improving situational awareness in electric power grid operation.” In Proceeding *18th IFAC World Congress* (on-line), pp. 12162–12170.

Y. Chen, Z. Huang, and M. Elizondo. 2012. “Value of faster computation for power grid operation.” In Proceeding *8th Power Plants Power System Control Symposium.*, pp. 242–247.

Y. Chen, Z. Huang, Y. Liu, M. Rice, and S. Jin. 2012. “Computational challenges for power system operation.” In Proceeding of the *45th Annual Hawaii International Conference on System Sciences*. (HICSS-45), Jan. , pp. 2141–2150. IEEE Computer Society Press, Washington, D.C.

M. A. Elizondo, Y. Chen, and Z. Huang. “Reliability value of fast state estimation on power systems,” in Proceeding *IEEE Power Energy Society Transmission and Distribution Conference and Exposition.*, May 2012.

Y. Chen, M. Rice, S. Jin, and Z. Huang, “Parallel state estimation assessment with practical data,” in Proceeding *IEEE Power Energy Society General Meeting*, 2013, to appear.

**Book Chapters**

Z. Huang and Y. Chen. 2012. “High-performance computing for advanced smart grid applications.” In *Smart Grids: Infrastructure, Technology, and Solutions*. Editor-in-Chief Stuart Borlase. CRC Press Taylor & Francis, Boca Raton, Florida. Jan.

Z. Huang and Y. Chen. 2013. “High-performance computing for smart grid analysis and operation.” In *High-Performance Computing for Real-Time Grid Analysis and Operation*, editors S. K. Khaitan, A. G. S. Aluru, and K. Gopalakrishnan. Springer Berlin Heidelberg.