Journal Home > Volume 26 , Issue 4
Tsinghua Science and Technology 2021, 26(4): 464-474 https://doi.org/10.26599/TST.2020.9010019
Open Access | Issue | Published: 04 January 2021

Improved Approximate Minimum Degree Ordering Method and Its Application for Electrical Power Network Analysis and Computation

Show Author's Information 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.
Keywords:
Approximate Minimum Degree and Minimum Length (AMDML), electrical power network analysis, elimination tree, numerical solution, ordering method
Cite this article:
Guo J, Liang H, Ai S, et al. 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. https://doi.org/10.26599/TST.2020.9010019
Download citation
EndNote(RIS)
BibTeX

733

Views

49

Downloads

Citations

6

Crossref

7

WoS

7

Scopus

2

CSCD

Abstract Full text About this article

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.


menu
Abstract
Full text
Outline
About this article

Improved Approximate Minimum Degree Ordering Method and Its Application for Electrical Power Network Analysis and Computation

Show Author's information 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.

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.

Keywords: Approximate Minimum Degree and Minimum Length (AMDML), electrical power network analysis, elimination tree, numerical solution, ordering method

References(24)

[1]
J. Cao, K. Meng, J. Wang, M. Yang, Z. Chen, W. Li, and C. Lin, An energy internet and energy routers, Scientia Sinica Informationis, vol. 44, no. 6, pp. 714-727, 2014.
Google Scholar
[2]
K. Wang, J. Yu, Y. Yu, Y. Qian, D. Zeng, S. Guo, Y. Xiang, and J. Wu, A survey on energy internet: Architecture, approach, and emerging technologies, IEEE Systems Journal, vol. 12, no. 3, pp. 2403-2416, 2018.
Google Scholar
[3]
Y. Ming, J. Yang, J. Cao, Z. Zhou, and C. Xing, Distributed energy sharing in energy internet through distributed averaging, Tsinghua Science and Technology, vol. 23, no. 3, pp. 233-242, 2018.
Google Scholar
[4]
G. Kamath, L. Shi, E. Chow, W. Song, and J. Yang, Decentralized multigrid for in-situ big data computing, Tsinghua Science and Technology, vol. 20, no. 6, pp. 545-559, 2015.
Google Scholar
[5]
L. Liu, X. Chen, Z. Lu, L. Wang, and X. Wen, 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.
Google Scholar
[6]
L. Tan, S. Kothapalli, and L. Chen, 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.
Google Scholar
[7]
J. Guo, J. Zhou, Q. Li, Y. Chen, Y. Luo, and Y. Lang, 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.
Google Scholar
[8]
M. A. Pai and H. Dag, 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]
Y. Wan, J. Cao, S. Zhang, G. Tu, C. Lu, X. Xu, and K. Li, An integrated cyber-physical simulation environment for smart grid applications, Tsinghua Science and Technology, vol. 19, no. 2, pp. 133-143, 2014.
Google Scholar
[10]
J. Shu, W. Xue, and W. Zheng, A parallel transient stability simulation for power systems, IEEE Transactions on Power Systems, vol. 20, no. 4, pp. 1709-1717, 2005.
Google Scholar
[11]
S. C. Eisenstat and J. W. H. Liu, Exploiting structural symmetry in unsymmetric sparse symbolic factorization, SIAM Journal of Matrix Analysis and Applications, vol. 13, no. 1, pp. 202-211, 1992.
Google Scholar
[12]
Y. Chen, Z. Huang, Y. Liu, M. J. Rice, and S. Jin, Computational challenges for power system operation, in Proceedings of 45th Hawaii International Conference on System Science, Maui, HI, USA, 2012, pp. 2141-2150.
[13]
B. Zhang, S. Chen, and Z. Yan, Advanced Electrical Power Network Analysis. Beijing, China: Tsinghua Press, 2007.
[14]
S. K. Khaitan, 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]
R. C. Green, L. Wang, and M. Alam, 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.
Google Scholar
[16]
Z. Huang, Y. Chen, and J. Nieplocha, Massive contingency analysis with high performance computing, in Proc. of IEEE Power and Energy Society General Meeting, Calgary, Canada, 2009, pp. 1-8.
[17]
L. Tan, S. Kothapalli, L. Chen, O. Hussaini, R. Bissiri, and Z. Chen, 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.
Google Scholar
[18]
Z. Li, V. D. Donde, J. Tournier, and F. Yang, 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]
A. Gomez and L. G. Franquelo, Node ordering algorithms for sparse vector method improvement, IEEE Transactions on Power Systems, vol. 3, no. 1, pp. 73-79, 1988.
Google Scholar
[20]
R. Betancourt, An efficient heuristic ordering algorithm for partial matrix refactorization, IEEE Transactions on Power Systems, vol. 3, no. 3, pp. 1181-1186, 1988.
Google Scholar
[21]
J. W. H. Liu, The role of elimination trees in sparse factorization, SIAM Journal of Matrix Analysis and Applications, vol. 11, no. 1, pp. 134-172, 1990.
Google Scholar
[22]
R. Betancourt, An efficient heuristic ordering algorithm for partial matrix refactorization, IEEE Transactions on Power Systems, vol. 3, no. 3, pp. 1181-1186, 1988.
Google Scholar
[23]
P. R. Amestroy, T. A. Davis, and I. S. Duff, Algorithm 837: AMD, an approximate minimum degree ordering algorithm, ACM Transactions Math Software, vol. 30, no. 3, pp. 381-388, 2004.
Google Scholar
[24]
R. D. Zimmerman, C. E. Murillo-Sanchez, and R. J. Thomas, 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.
Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 19 February 2020
Accepted: 19 April 2020
Published: 04 January 2021
Issue date: August 2021

Copyright

© The author(s) 2021

Acknowledgements

This work was supported in part by the National Key Basic Research and Development Program of China (No. 2017YFE0132100), the Tsinghua-Toyota Research Fund (No. 20203910016), and the BNRist Program (No. BNR2020TD01009).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return