Please wait a minute...
Tsinghua Science and Technology  2021, Vol. 26 Issue (4): 464-474    doi: 10.26599/TST.2020.9010019
    
Improved Approximate Minimum Degree Ordering Method and Its Application for Electrical Power Network Analysis and Computation
Jian Guo(),Hong Liang(),Songpu Ai(),Chao Lu(),Haochen Hua(),Junwei Cao*()
Beijing National Research Center for Information Science and Technology, Beijing 100084, China.
Department of Electrical Engineering, Tsinghua University, Beijing 100084, China.
College of Energy and Electrical Engineering, Hohai University, Nanjing 211100, China.
Download: PDF (5728 KB)      HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

Electrical power network analysis and computation play an important role in the planning and operation of the power grid, and they are modeled mathematically as differential equations and network algebraic equations. The direct method based on Gaussian elimination theory can obtain analytical results. Two factors affect computing efficiency: the number of nonzero element fillings and the length of elimination tree. This article constructs mapping correspondence between eliminated tree nodes and quotient graph nodes through graph and quotient graph theories. The Approximate Minimum Degree (AMD) of quotient graph nodes and the length of the elimination tree nodes are composed to build an Approximate Minimum Degree and Minimum Length (AMDML) model. The quotient graph node with the minimum degree, which is also the minimum length of elimination tree node, is selected as the next ordering vector. Compared with AMD ordering method and other common methods, the proposed method further reduces the length of elimination tree without increasing the number of nonzero fillings; the length was decreased by about 10% compared with the AMD method. A testbed for experiment was built. The efficiency of the proposed method was evaluated based on different sizes of coefficient matrices of power flow cases.



Key wordsApproximate Minimum Degree and Minimum Length (AMDML)      electrical power network analysis      elimination tree      numerical solution      ordering method     
Received: 19 February 2020      Published: 12 January 2021
Fund:  National Key Basic Research and Development Program of China(2017YFE0132100);Tsinghua-Toyota Research Fund(20203910016);BNRist Program(BNR2020TD01009)
Corresponding Authors: Junwei Cao     E-mail: guoj2019@tsinghua.edu.cn;lianghong@mail.tsinghua.edu.cn;aisp@mail.tsinghua.edu.cn;luchao@ tsinghua.edu.cn;huahc16@tsinghua.org.cn;jcao@tsinghua.edu.cn
About author: Jian Guo received the BS and MS degrees in computer science from Taiyuan University of Technology, Taiyuan, China in 2008 and North China Electric Power University, Beijing, China in 2011, respectively, and the PhD degree in electrical engineering from China Electrical Power Research Institute, Beijing, China in 2018. He is currently a postdoctoral researcher with the Department of Electrical Engineering, Tsinghua University, and working as a research assistant in Beijing National Research Center for Information Science and Technology, Beijing, China. His research interests include online analysis, high-performance computation, and their applications in power system and the energy internet.|Hong Liang received the BS degree in computational mathematics from Wuhan University, Wuhan, China in 2013 and the PhD degree in applied mathematics from Tsinghua University, Beijing, China in 2019. She is currently a postdoctoral researcher with the Research Institute of Information Technology, Tsinghua University. Her research interests include control and optimization, machine learning, and their applications in power system and the energy internet.|Songpu Ai received BS degree in mathematics and applied mathematics from Shandong University, Jinan, China in 2012, the MS degree in information and communication technology from University of Agder, Norway in 2015, and the PhD degree in information technology from University of Stavanger, Norway in 2019. He is currently a postdoctoral researcher in the Research Institute of Information Technology, Tsinghua University. His current research interests include blockchain, big data, and artificial intelligence and their applications in power systems, smart grids, and the energy internet.|Chao Lu received the BEng and PhD degrees from Tsinghua University in 1999 and 2005, respectively. He is currently an assistant professor at the Department of Electrical Engineering, Tsinghua University, China. His research interests include power system analysis and control, and intelligent control applications.|Haochen Hua received the BS degree in mathematics with finance in 2011 and the PhD degree in mathematical sciences in 2016, both from the University of Liverpool, Liverpool, UK. From 2016 to 2019. He was a postdoctoral fellow in the Research Institute of Information Technology, Tsinghua University. Since 2020, he has been a professor in the College of Energy and Electrical Engineering, Hohai University, Nanjing, China. His current research interests include optimal and robust control theory and its applications in power systems, smart grids, and energy internet.|Junwei Cao received the PhD degree in computer science from University of Warwick, UK in 2001. He received the MEng and BEng degrees from Tsinghua University in 1998 and 1996, respectively. He is currently a professor and deputy director of Research Institute of Information Technology, Tsinghua University, China. He is also the director of Open Platform and Technology Division, Tsinghua National Laboratory for Information Science and Technology. Before joining Tsinghua University in 2006, he was a research scientist of Massachusetts Institute of Technology, USA. Before that he worked as a research staff member of NEC Europe Ltd., Germany. He has published over 130 academic papers and books, which were cited by international researchers for over 3000 times. He is a senior member of the IEEE Computer Society and a member of the ACM and CCF. His research interests include advanced computing technology and applications.
Cite this article:

Jian Guo,Hong Liang,Songpu Ai,Chao Lu,Haochen Hua,Junwei Cao. Improved Approximate Minimum Degree Ordering Method and Its Application for Electrical Power Network Analysis and Computation. Tsinghua Science and Technology, 2021, 26(4): 464-474.

URL:

http://tst.tsinghuajournals.com/10.26599/TST.2020.9010019     OR     http://tst.tsinghuajournals.com/Y2021/V26/I4/464

Fig. 1 Diagram of functional maxIterations.
ApplicationType of numerical solutions
N-1 sercurity analysisFactorization/sparse linear equations
Short circuitFactorization/sparse linear equations
Transient computationDifferential/sparse linear equations
Optimal power flowSparse linear equations with constraints
Power flowSparse linear equations
State estimationSparse linear equations
Table 1 Numerical computing types of power system.
Fig. 2 Numerical solutions for electrical network analysis.
Fig. 3 Elimination tree diagram.
Fig. 4 Example of quotient graph.
Fig. 5 AMDML ordering process.
StepApproximate minimum degrees of quotient graph nodes (1-10)Length of graph nodes (1-10)Selected node
1{2, 3, 3, 3, 4, 3, 6, 4, 5, 3}{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}1
2{2, 3, 3, 3, 4, 3, 6, 4, 5, 3}{0, 0, 0, 1, 0, 1, 0, 0, 0, 0}10
3{2, 3, 3, 3, 4, 3, 5, 3, 4, 3}{0, 0, 0, 1, 0, 1, 1, 1, 1, 0}3
4{2, 3, 3, 3, 4, 4, 5, 3, 4, 3}{0, 0, 0, 1, 1, 1, 1, 1, 1, 0}2
5{2, 3, 3, 3, 3, 4, 5, 3, 4, 3}{0, 0, 0, 1, 1, 1, 1, 1, 1, 0}5
6{2, 3, 3, 3, 3, 3, 4, 3, 3, 3}{0, 0, 0, 1, 1, 2, 2, 1, 2, 0}4
7{2, 3, 3, 3, 3, 3, 3, 3, 3, 3}{0, 0, 0, 1, 1, 2, 2, 2, 2, 0}7
Table 2 Value changes of properties in the AMDML-based elimination process.
𝟏𝟎×𝟏𝟎 symbolic matrix.
">
Fig. 6 𝟏𝟎×𝟏𝟎 symbolic matrix.
Fig. 7 Quotient graph.
Fig. 8 Reduction graph.
Fig. 9 Comparison of ordering methods in symbolic analysis phase.
Case nameNumber of branchesJacobian matrix
Case 300411530×530
Case 135419912447×2447
Case 312036935991×5991
Case 924116 04917 036×17 036
Case 13 65920 46723 225×23 225
Table 3 Information of test cases.
MethodMDMD-MLAMDAMDML
LenALFrT (ms)LenALFrT (ms)LenALFrT (ms)LenALFrT (ms)
Case 3005429.31.480.144830.41.490.215831.31.490.105429.81.460.1
Case 13549348.71.401.407344.91.411.808348.31.390.906741.61.381.0
Case 3120160100.01.723.0011080.21.724.0014385.81.681.3012685.81.691.2
Case 9241300183.61.738.00234166.11.7410.00286197.01.684.00260184.31.664.3
Case 13 659279181.51.6710.00220149.31.6413.50301202.61.645.00286198.41.645.2
Table 4 Characteristic parameter of the elimination tree under different ordering methods.
Case nameIterationNaN (ms)MD-ML (ms)AMD (ms)AMDML (ms)
Case 300513302012
Case 1354456453130
Case 31206600127107100
Case 924167900454390340
Case 13 659519 820694430370
Table 5 Comparison of Newton-Raphson power flow computation time.
Case nameIterationNaN (ms)MD-ML (ms)AMD (ms)AMDML (ms)
Case 30094543
Case 13548131087
Case 31201364342621
Case 9241145301558070
Case 13 65914105023711092
Table 6 Comparison of P-Q power flow computation time.
[1]   Cao J., Meng K., Wang J., Yang M., Chen Z., Li W., and Lin C., An energy internet and energy routers, Scientia Sinica Informationis, vol. 44, no. 6, pp. 714-727, 2014.
[2]   Wang K., Yu J., Yu Y., Qian Y., Zeng D., Guo S., Xiang Y., and Wu J., A survey on energy internet: Architecture, approach, and emerging technologies, IEEE Systems Journal, vol. 12, no. 3, pp. 2403-2416, 2018.
[3]   Ming Y., Yang J., Cao J., Zhou Z., and Xing C., Distributed energy sharing in energy internet through distributed averaging, Tsinghua Science and Technology, vol. 23, no. 3, pp. 233-242, 2018.
[4]   Kamath G., Shi L., Chow E., Song W., and Yang J., Decentralized multigrid for in-situ big data computing, Tsinghua Science and Technology, vol. 20, no. 6, pp. 545-559, 2015.
[5]   Liu L., Chen X., Lu Z., Wang L., and Wen X., Mobile-edge computing framework with data compression for wireless network in energy internet, Tsinghua Science and Technology, vol. 24, no. 3, pp. 271-280, 2019.
[6]   Tan L., Kothapalli S., and Chen L., A survey of power and energy efficient techniques for high performance numerical linear algebra operations, Parallel Computing, vol. 40, no. 10, pp. 559-573, 2014.
[7]   Guo J., Zhou J., Li Q., Chen Y., Luo Y., and Lang Y., Current status of high-performance on-line analysis computation and key technologies for cooperating computation, Automation of Electric Power Systems, vol. 42, no. 3, pp. 149-159, 2018.
[8]   Pai M. A. and Dag H., Iterative solver techniques in large scale power system computation, in Proceedings of the 36th IEEE Conference on Decision and Control, San Diego, CA, USA, 1997, pp. 3861-3866.
[9]   Wan Y., Cao J., Zhang S., Tu G., Lu C., Xu X., and Li K., An integrated cyber-physical simulation environment for smart grid applications, Tsinghua Science and Technology, vol. 19, no. 2, pp. 133-143, 2014.
[10]   Shu J., Xue W., and Zheng W., A parallel transient stability simulation for power systems, IEEE Transactions on Power Systems, vol. 20, no. 4, pp. 1709-1717, 2005.
[11]   Eisenstat S. C. and Liu J. W. H., Exploiting structural symmetry in unsymmetric sparse symbolic factorization, SIAM Journal of Matrix Analysis and Applications, vol. 13, no. 1, pp. 202-211, 1992.
[12]   Chen Y., Huang Z., Liu Y., Rice M. J., and Jin S., Computational challenges for power system operation, in Proceedings of 45th Hawaii International Conference on System Science, Maui, HI, USA, 2012, pp. 2141-2150.
[13]   Zhang B., Chen S., and Yan Z., Advanced Electrical Power Network Analysis. Beijing, China: Tsinghua Press, 2007.
[14]   Khaitan S. K., A survey of high-performance computing approaches in power systems, in Proceedings of IEEE Power and Energy Society General Meeting, Boston, MA, USA, 2016, pp. 1-6.
[15]   Green R. C., Wang L., and Alam M., Applications and trends of high performance computing for electric power systems focusing on smart grid, IEEE Transactions on Smart Grid, vol. 4, no. 2, pp. 922-931, 2013.
[16]   Huang Z., Chen Y., and Nieplocha J., Massive contingency analysis with high performance computing, in Proc. of IEEE Power and Energy Society General Meeting, Calgary, Canada, 2009, pp. 1-8.
[17]   Tan L., Kothapalli S., Chen L., Hussaini O., Bissiri R., and Chen Z., A survey of power and energy efficient techniques for high performance numerical linear algebra operations, IEEE Transactions on Parallel Computing, vol. 40, no. 10, pp. 559-573, 2014.
[18]   Li Z., Donde V. D., Tournier J., and Yang F., On limitation of traditional multi-core and potential of many-Core processing architectures for sparse linear solvers used in large-scale power system applications, in Proceedings of IEEE Power and Energy Society General Meeting, Detroit, MI, USA, 2011, pp. 1-8.
[19]   Gomez A. and Franquelo L. G., Node ordering algorithms for sparse vector method improvement, IEEE Transactions on Power Systems, vol. 3, no. 1, pp. 73-79, 1988.
[20]   Betancourt R., An efficient heuristic ordering algorithm for partial matrix refactorization, IEEE Transactions on Power Systems, vol. 3, no. 3, pp. 1181-1186, 1988.
[21]   Liu J. W. H., The role of elimination trees in sparse factorization, SIAM Journal of Matrix Analysis and Applications, vol. 11, no. 1, pp. 134-172, 1990.
[22]   Betancourt R., An efficient heuristic ordering algorithm for partial matrix refactorization, IEEE Transactions on Power Systems, vol. 3, no. 3, pp. 1181-1186, 1988.
[23]   Amestroy P. R., Davis T. A., and Duff I. S., Algorithm 837: AMD, an approximate minimum degree ordering algorithm, ACM Transactions Math Software, vol. 30, no. 3, pp. 381-388, 2004.
[24]   Zimmerman R. D., Murillo-Sanchez C. E., and Thomas R. J., MATPOWER: Steady-state operations, planning, and analysis tools for power systems research and education, IEEE Transactions on Power Systems, vol. 26, no. 1, pp. 12-19, 2011.
No related articles found!