Home Tsinghua Science and Technology Article
PDF (5.6 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Open Access

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

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.
Show Author Information

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 analysiselimination treenumerical solutionordering method

References

[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
Tsinghua Science and Technology
Volume 26 Issue 4,
August 2021
Pages 464-474
DOI: 10.26599/TST.2020.9010019
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
Metrics & Citations  
Article History
Copyright
Rights and Permissions
Return