research-article

Evaluation of overlapping restricted additive schwarz preconditioning for parallel solution of very large power flow problems

Authors:

Shrirang Abhyankar,

Emil ConstantinescuAuthors Info & Claims

HiPCNA-PG '13: Proceedings of the 3rd International Workshop on High Performance Computing, Networking and Analytics for the Power Grid

Article No.: 5, Pages 1 - 8

https://doi.org/10.1145/2536780.2536784

Published: 17 November 2013 Publication History

Abstract

The computational bottleneck for large nonlinear AC power flow problems using Newton's method is the solution of the linear system at each iteration. We present a parallel linear solution scheme using the Krylov subspace-based iterative solver GMRES preconditioned with overlapping restricted additive Schwarz method (RASM) that shows promising speedup for this linear system solution. This paper evaluates the performance of RASM with different amounts of overlap and presents its scalability and convergence behavior for three large power flow problems consisting of 22,996, 51,741, and 91,984 buses respectively.

References

[1]

S. Abhyankar and A. Flueck, "Real-time power system dynamics simulation using a parallel block-jacobi preconditioned Newton-GMRES scheme," in Proceedings of the 2^nd International Workshop on High Performance Computing, Networking and Analytics for the Power Grid. IEEE, 2012.

Digital Library

[2]

S. Abhyankar, B. Smith, H. Zhang, and A. Flueck, "Using PETSc to develop scalable applications for next-generation power grid," in Proceedings of the 1st International Workshop on High Performance Computing, Networking and Analytics for the Power Grid. ACM, 2011. {Online}. Available: http://www.mcs.anl.gov/uploads/cels/papers/P1957-0911.pdf

Digital Library

[3]

R. Bacher and W. F. Tinney, "Faster local power flow solutions: the zero mismatch approach," IEEE Transactions on Power Systems, vol. 4, no. 4, pp. 1345--1354, 1989.

[4]

S. Balay, J. Brown, K. Buschelman, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, B. F. Smith, and H. Zhang, "PETSc users manual," Argonne National Laboratory, Tech. Rep. ANL-95/11 - Revision 3.3, 2013. {Online}. Available: http://www.mcs.anl.gov/petsc

[5]

X. C-Cai and M. Sarkis, "A restricted additive Schwarz preconditioner for general sparse linear systems," SIAM Journal of Scientific Computing, vol. 21, pp. 792--797, 1999.

Digital Library

[6]

X.-C. Cai and Y. Saad, "Overlapping domain decomposition algorithms for general sparse matrices," Numerical Linear Algebra Applications, vol. 3, pp. 221--237, 1996.

[7]

X. C. Cai and O. B. Widlund, "Multiplicative Schwarz algorithms for non symmetric and indefinite elliptic problems," SIAM Journal of Numerical Analysis, vol. 30, pp. 936--952, 1993.

Digital Library

[8]

T. Chan and T. Mathew, "Domain decomposition algorithms," Acta Numerica, pp. 61--143, 1994.

[9]

T. Chan, J. R. Gilbert, and S.-H. Teng, "Geometric spectral partitioning," ftp.parc.xerox.com, 1994.

[10]

S.-D. Chen and J.-F. Chen, "Fast load flow using multiprocessors," International Journal of Electrical Power and Energy Systems, vol. 22, pp. 231--236, 2000.

[11]

V. M. da Costa and A. L. S. Rosa, "A comparative analysis of different power flow methodologies," IEEE Transactions on Power Systems, no. 978-1-4244-2218-0, 2008.

[12]

V. M. da Costa, N. Martins, and J. L. R. Pereira, "Developments in the Newton-Raphson power flow formulation based on current injections," IEEE Transactions on Power Systems, vol. 14, no. 4, pp. 1320--1326, 1999.

[13]

H. Dag and G. Soykan, "Power flow using thread programming," in Proceedings of IEEE PowerTech conference, 2011, pp. 1--5.

[14]

J. Demmel, J. Gilbert, and X. Li, "SuperLU Web page," http://crd.lbl.gov/xiaoye/SuperLU.

[15]

M. Dryja and O. B. Widlund, "Domain decomposition algorithms with small overlap," SIAM Journal of Scientific Computating, vol. 15, pp. 604--620, 1994.

Digital Library

[16]

ERCOT, "Electrical buses and outage scheduling," August 2006, http://nodal.ercot.com.

[17]

A. G. Exposito and E. R. Ramos, "Augmented rectangular load flow model," IEEE Transactions on Power Systems, vol. 17, no. 2, pp. 271--276, 2002.

[18]

A. Flueck and H. Chiang, "Solving the nonlinear power flow equations with an inexact newton method using GMRES," IEEE Transactions on Power Systems, vol. 13, pp. 267--273, 1998.

[19]

A. George and J. W. H. Liu, "A fast implementation of the minimum degree algorithm using quotient graphs," ACM Transactions on Mathematical Software, vol. 6, pp. 337--358, 1980.

Digital Library

[20]

A. Gopal, D. Niebur, and S. Venkatasubramaniam, "DC power flow based contingency analysis using graphics processing units," in Proceedings of IEEE PowerTech conference, 2007, pp. 731--736.

[21]

S. Grijalva, "Research needs in multi-dimensional, multi-scale modeling and algorithms for next generation electricity grids," in DOE workshop on computing challenges for the next-generation power grid, 2011.

[22]

B. Hendrickson and R. Leland, "The chaco user's guide version 2.0," Sandia National Laboratories, Tech. Rep., 1995.

[23]

P. Interconnection, "Pjm statistics," February 2011, http://www.pjm.com.

[24]

J. Izaguirre, "An empirical evaluation of graph partitioning algorithms," Master's thesis, University of Illinois at Urbana Champaign, 1996.

[25]

A. A. Kamiabad, "Implementing a preconditioned iterative linear solver using a massively parallel graphics processing units," Master's thesis, University of Toronto, 2011.

[26]

G. Karypis and V. Kumar, "ParMETIS: Parallel graph partitioning and sparse matrix ordering library," Department of Computer Science, University of Minnesota, Tech. Rep. 97-060, 1997, http://www.cs.umn.edu/metis.

[27]

B. W. Kerninghan and S. Lin, "An efficient heuristic procedure for partitioning graphs," Bell System Technical Journal, vol. 49, pp. 291--307, 1970.

[28]

G. Luo and A. Semlyen, "Efficient load flow for large weakly meshed networks," IEEE Transactions on Power Systems, vol. 5, no. 4, pp. 1309--1316, 1990.

[29]

A. Pothen, H. Simon, and K. Liou, "Partitioning sparse matrices with eigenvectors of graphs," SIAM Journal of Matrix Analysis Applications, vol. 11, pp. 430--452, 1990.

Digital Library

[30]

Y. Saad, Iterative Methods for Sparse Linear Systems. SIAM, 2000.

Digital Library

[31]

A. Semlyen, "Fundamental concepts of a Krylov subspace power flow methodology," IEEE Transactions on Power Systems, vol. 11, no. 3, pp. 1528--1537, 1996.

[32]

B. Smith, P. Bjorstad, and W. Gropp, Domain decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University, 1996.

Digital Library

[33]

B. Stott and O. Alsac, "Fast decoupled load flow," IEEE Transactions on Power Systems, vol. 17, no. no. 3: 859--869, 1974.

[34]

J. Tate and T. Overbye, "A comparison of the optimal multiplier in polar and rectangular coordinates," IEEE Transactions on Power Systems, vol. 20, pp. 1667--1674, 2005.

[35]

W. F. Tinney and C. E. Hart, "Power flow solution by Newton's method," IEEE Transactions on Power Systems, vol. PAS-86: 1449--1456, 1967.

[36]

F. Tu and A. Flueck, "A message-passing distributed-memory Newton-GMRES parallel power flow algorithm," in Proceedings of IEEE Power Engineering Society Summer Meeting, vol. 3, 2002, pp. 1477--1482.

[37]

F. Tu and A. Flueck, "A message-passing distributed-memory parallel power flow algorithm," in Proceedings of IEEE Power Engineering Society Winter Meeting, vol. 1, 2002, pp. 211--216

[38]

J. Q. Wu and A. Bose, "Parallel solution of large sparse matrix equations and parallel power flow," IEEE Transactions on Power Systems, vol. 10, pp. 1343--1349, 1995.

[39]

R. Zimmerman and C. Murillo-Sanchez, "Matpower 4.0 users manual," Power Systems Engineering Research Center, Tech. Rep., 2011.

Cited By

Sundermann RAbhyankar SZhang HKimn JHansen T(2022)Parallel primal‐dual interior point method for the solution of dynamic optimal power flowIET Generation, Transmission & Distribution10.1049/gtd2.1270817:4(811-820)Online publication date: 30-Dec-2022
https://doi.org/10.1049/gtd2.12708
Lee BPereira Batista E(2020)Algebraic multigrid for the nonlinear powerflow equationsNumerical Linear Algebra with Applications10.1002/nla.234728:2Online publication date: 9-Nov-2020
https://doi.org/10.1002/nla.2347
Schroder JFalgout RWoodward CTop PLecouvez M(2018)Parallel-in-Time Solution of Power Systems with Scheduled Events2018 IEEE Power & Energy Society General Meeting (PESGM)10.1109/PESGM.2018.8586435(1-5)Online publication date: Aug-2018
https://doi.org/10.1109/PESGM.2018.8586435
Show More Cited By

Index Terms

Evaluation of overlapping restricted additive schwarz preconditioning for parallel solution of very large power flow problems
1. Applied computing
  1. Physical sciences and engineering
    1. Engineering
2. Computing methodologies
  1. Modeling and simulation

Recommendations

The right–left preconditioning technique for the solution of the large matrix equation AXB = C

In this paper, the linear matrix equation <inline-formula><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink="gcom_a_1045420_ilm0001.gif"/></inline-formula> is considered, where <inline-formula><inline-graphic xmlns:xlink="http://...
Simultaneous solution of large-scale linear systems and eigenvalue problems with a parallel GMRES method

A method for simultaneous solution of large and sparse linearized equation sets and the corresponding eigenvalue problems is presented. Such problems arise from the discretization and the solution of nonlinear problems with the finite element method and ...
Preconditioned GMRES methods with incomplete Givens orthogonalization method for large sparse least-squares problems

We propose to precondition the GMRES method by using the incomplete Givens orthogonalization (IGO) method for the solution of large sparse linear least-squares problems. Theoretical analysis shows that the preconditioner satisfies the sufficient ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

HiPCNA-PG '13: Proceedings of the 3rd International Workshop on High Performance Computing, Networking and Analytics for the Power Grid

November 2013

49 pages

ISBN:9781450325103

DOI:10.1145/2536780

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 November 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SC13

Sponsor:

SC13: International Conference for High Performance Computing, Networking, Storage and Analysis

November 17 - 22, 2013

Colorado, Denver

Acceptance Rates

HiPCNA-PG '13 Paper Acceptance Rate 5 of 7 submissions, 71%;

Overall Acceptance Rate 15 of 17 submissions, 88%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
112
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sundermann RAbhyankar SZhang HKimn JHansen T(2022)Parallel primal‐dual interior point method for the solution of dynamic optimal power flowIET Generation, Transmission & Distribution10.1049/gtd2.1270817:4(811-820)Online publication date: 30-Dec-2022
https://doi.org/10.1049/gtd2.12708
Lee BPereira Batista E(2020)Algebraic multigrid for the nonlinear powerflow equationsNumerical Linear Algebra with Applications10.1002/nla.234728:2Online publication date: 9-Nov-2020
https://doi.org/10.1002/nla.2347
Schroder JFalgout RWoodward CTop PLecouvez M(2018)Parallel-in-Time Solution of Power Systems with Scheduled Events2018 IEEE Power & Energy Society General Meeting (PESGM)10.1109/PESGM.2018.8586435(1-5)Online publication date: Aug-2018
https://doi.org/10.1109/PESGM.2018.8586435
Abhyankar SConstantinescu ESmith BFlueck AMaldonado D(2017)Parallel Dynamics Simulation Using a Krylov-Schwarz Linear Solution SchemeIEEE Transactions on Smart Grid10.1109/TSG.2016.26108638:3(1378-1386)Online publication date: May-2017
https://doi.org/10.1109/TSG.2016.2610863

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents