Beijing National Research Center for Information Science and Technology, Beijing100084, China. Department of Electrical Engineering, Tsinghua University, Beijing100084, China. College of Energy and Electrical Engineering, Hohai University, Nanjing211100, China.

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.

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.

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.

Fig. 9Comparison of ordering methods in symbolic analysis phase.

Case name

Number of branches

Jacobian matrix

Case 300

411

530$\times $530

Case 1354

1991

2447$\times $2447

Case 3120

3693

5991$\times $5991

Case 9241

16 049

17 036$\times $17 036

Case 13 659

20 467

23 225$\times $23 225

Table 3Information of test cases.

Method

MD

MD-ML

AMD

AMDML

${L}_{\text{en}}$

AL

Fr

$T$ (ms)

${L}_{\text{en}}$

AL

Fr

$T$ (ms)

${L}_{\text{en}}$

AL

Fr

$T$ (ms)

${L}_{\text{en}}$

AL

Fr

$T$ (ms)

Case 300

54

29.3

1.48

0.14

48

30.4

1.49

0.21

58

31.3

1.49

0.10

54

29.8

1.46

0.1

Case 1354

93

48.7

1.40

1.40

73

44.9

1.41

1.80

83

48.3

1.39

0.90

67

41.6

1.38

1.0

Case 3120

160

100.0

1.72

3.00

110

80.2

1.72

4.00

143

85.8

1.68

1.30

126

85.8

1.69

1.2

Case 9241

300

183.6

1.73

8.00

234

166.1

1.74

10.00

286

197.0

1.68

4.00

260

184.3

1.66

4.3

Case 13 659

279

181.5

1.67

10.00

220

149.3

1.64

13.50

301

202.6

1.64

5.00

286

198.4

1.64

5.2

Table 4Characteristic parameter of the elimination tree under different ordering methods.

Case name

Iteration

NaN (ms)

MD-ML (ms)

AMD (ms)

AMDML (ms)

Case 300

5

13

30

20

12

Case 1354

4

56

45

31

30

Case 3120

6

600

127

107

100

Case 9241

6

7900

454

390

340

Case 13 659

5

19 820

694

430

370

Table 5Comparison of Newton-Raphson power flow computation time.

Case name

Iteration

NaN (ms)

MD-ML (ms)

AMD (ms)

AMDML (ms)

Case 300

9

4

5

4

3

Case 1354

8

13

10

8

7

Case 3120

13

64

34

26

21

Case 9241

14

530

155

80

70

Case 13 659

14

1050

237

110

92

Table 6Comparison 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.