Application of KLU Sparse Direct Linear Solver in State Estimation

doi:10.11930/j.issn.1004-9649.201806130

Abstract

Abstract: Solving sparse matrix and linear equation is an important computational kernel in large-scale power system state estimation. This paper embeds the BTF and Gilbert-Peierls algorithm-based KLU sparse direct linear solver into the state estimation program of smart grid operation supporting systems. Firstly, based on the computation of the measurement jacobi matrix, the OpenMP parallelization technology is used to solve G which called gain matrix; and then, symbolic analysis and numerical factorization of G are handled by KLU solver; finally, the KLU solver is used to solve the linear equations in the process of state estimation, thus significantly improving the computational efficiency of state estimation in large-scale power network. The effectiveness and practicality of the proposed method are verified through practical application in D5000 system of provincial power company and model data dispatch centers.

Key words: power system, state estimation, sparse matrix, left-looking LU factorization, multi-process, KLU sparse solver

CLC Number:

TM711

LUO Yuchun, WANG Yi, SHAN Xin, ZOU Dehu. Application of KLU Sparse Direct Linear Solver in State Estimation[J]. Electric Power, 2019, 52(2): 111-118.

Add to citation manager EndNote|Ris|BibTeX

URL: https://www.electricpower.com.cn/EN/10.11930/j.issn.1004-9649.201806130

https://www.electricpower.com.cn/EN/Y2019/V52/I2/111

References

[1] 王永, 郭志忠, 彭茂君, 等. 基于灵敏度分析的多区域互联电力系统状态估计[J]. 电力系统自动化, 2007, 19(31):27-31 WANG Yong, GUO Zhizhong, PENG Maojun, et al. State estimation of a multi-area interconnected power system based on sensitivity analysis[J]. Automation of Electric Power Systems, 2007, 19(31):27-31
[2] 王建, 陈颖, 黄少伟, 等. 基于KKT条件分解的互联电网分布式状态估计算法[J]. 电力系统自动化, 2010, 34(19):31-36 WANG Jian, CHEN Ying, HUANG Shaowei, et al. A distributed state estimation method for interconnected power grid based on decomposition of KKT condition[J]. Automation of Electric Power Systems, 2010, 34(19):31-36
[3] 王耀瑜, 余贻鑫. 分布式能量管理系统(DEMS)状态估计分布式异步迭代算法[J]. 中国电机工程学报, 1996, 16(3):160-164 WANG Yaoyu, YU Yixin. Distributed energy management system (DEMS) asynchronous iteration state estimation[J]. Proceedings of the CSEE, 1996, 16(3):160-164
[4] 高毅, 王成山, 李继平. 改进十字链表的稀疏矩阵技术及其在电力系统仿真中的应用[J]. 电网技术, 2011, 35(5):33-36 GAO Yi, WANG Chengshan, LI Jiping. An improved cross chain table based sparse matrix technology and its application in power system simulation[J]. Power System Technology, 2011, 35(5):33-36
[5] 朱凌志, 安宁. 基于二维链表的稀疏矩阵在潮流计算中的应用[J]. 电网技术, 2005, 29(8):51-55 ZHU Lingzhi, AN Ning. Application of two-dimensional chain table based sparse matrix in power flow calculation[J]. Power System Technology, 2005, 29(8):51-55
[6] 陈荃韡, 龚成明, 赵晋泉, 等. 并行稀疏系统直接求解库SuperLU_MT在状态估计中的应用[J]. 电力系统自动化, 2017, 41(3):83-88 CHEN Quanwei, GONG Chengming, ZHAO Jinquan, et al. Application of parallel sparse system direct solver library SuperLU_MT in state estimation[J]. Automation of Electric Power Systems, 2017, 41(3):83-88
[7] 宁剑, 王毅, 邹德虎, 等. 状态估计智能分析功能设计与应用[J]. 中国电力, 2015, 48(2):85-89 NING Jian, WANG Yi, ZOU Dehu, et al. Design and application of state estimation intelligent analysis[J]. Electric Power, 2015, 48(2):85-89
[8] DAVIS T A, HU Yifan. The university of Florida sparse matrix collection[J]. ACM Transactions on Mathematical Software, 2011, 38(1):1-25.
[9] DAVIS T A, NATARAJAN E P. Algorithm 907:KLU, a direct sparse solver for circuit simulation problems[J]. ACM Transactions on Mathematical Software, 2010, 37(3):36:1-36:17.
[10] DUFF I S. On algorithms for obtaining a maximum transversal[J]. ACM Transactions on Mathematical Software, 1981, 7(3):315-330.
[11] DUFF I S. Algorithm 575:Permutations for a zero-free diagonal[J]. ACM Transactions on Mathematical Software, 1981, 7(3):387-390.
[12] DUFF I S, REID J K. An implementation of Tarjan's algorithm for the block triangularization of a matrix[J]. ACM Transactions on Mathematical Software, 1978, 4(2):137-147.
[13] DUFF I S, REID J K. Algorithm 529:Permutations to block triangular form[J]. ACM Transactions on Mathematical Software, 1978, 4(2):189-192.
[14] AMESTOY P R, DAVIS T A, DUFF I S. An approximate minimum degree ordering algorithm[J]. SIAM J. Matrix Anal. & Applic., 1996, 17(4):886-905.
[15] 唐灿, 郭睿, 顾黎强, 等. 基于图分割的潮流计算中的节点优化编号[J]. 中国电力, 2017, 50(4):52-58 TANG Can, GUO Rui, GU Liqiang, et al. Node ordering in power flow calculation based on graph partitioning algorithm[J]. Electric Power, 2017, 50(4):52-58
[16] GILBERT J R, NG E G. Predicting structure in nonsymmetric sparse matrix factorizations[M]. New York:Springer, 1992.
[17] DAVIS T A. Direct methods for sparse linear systems[M]. Philadelphia:SIAM, 2006.
[18] GILBERT J R, TIM PEIERLS T. Sparse partial pivoting in time proportional to arithmetic operations[J]. SIAM Journal on Scientific & Statistical Computing, 1988, 9(9):862-874.
[19] 罗玉春, 王毅, 戴则梅, 等. 基于多调度控制中心的分解协调状态估计[J]. 电网技术, 2016, 40(5):1516-1521 LUO Yuchun, WANG Yi, DAI Zemei, et al. Decomposition and coordination state estimation for multi dispatching and control centers[J]. Power System Technology, 2016, 40(5):1516-1521
[20] 姚诸香, 郭烨, 郭玉金, 等. 含指数型目标函数的电力系统抗差状态估计方法在江西电网中的应用[J]. 电网技术, 2012, 36(4):155-159 YAO Zhuxiang, GUO Ye, GUO Yujin, et al. Application of a robust state estimator based on maximum exponential square in Jiangxi power system[J]. Power System Technology, 2012, 36(4):155-159
[21] 厉超, 卫志农, 倪明, 等. 基于变量代换内点法的加权最小绝对值抗差状态估计[J]. 电力系统自动化, 2015, 39(6):48-52 LI Chao, WEI Zhinong, NI Ming, et al. WLAV robust state estimation based on variable substitution interior point method[J]. Automation of Electric Power Systems, 2015, 39(6):48-52
[22] 王雅婷, 何光宇, 刘铠诚, 等. 求解状态估计问题的内点半定规划法[J]. 电网技术, 2012, 36(10):209-215 WANG Yating, HE Guangyu, LIU Kaicheng, et al. An semi-definite programming method for state estimation problem[J]. Power System Technology, 2012, 36(10):209-215
[23] 张伯明, 陈寿孙, 严正. 高等电力网络分析[M]. 北京:清华大学出版社, 2007:58-62.
[24] 颜伟, 黄正波, 余娟, 等. 牛顿法潮流计算的高效综合稀疏技术[J]. 中国电力, 2010, 43(7):19-23 YAN Wei, HUANG Zhengbo, YU Juan, et al. Integrated sparse technique of Newton power flow calculation[J]. Electric Power, 2010, 43(7):19-23
[25] Peter S. Pacheco. 并行程序设计导论[M]. 邓倩妮, 译. 北京:机械工业出版社, 2016:139-143
[26] 龚成明, 於益军, 路轶, 等. 加权最小二乘状态估计量测权值计算的实用方法[J]. 电力系统自动化, 2016, 40(11):143-147 GONG Chengming, YU Yijun, LU Yi, et al. Practical method for calculating measurement weights in weighted least square state estimation[J]. Automation of Electric Power Systems, 2016, 40(11):143-147