Computational complexity in power systems

Abstract

The problem of estimating the increase in computational effort as the system size n increases is studied for methods requiring the solution of Ax = b, where A is sparse and topology-symmetric. The expected value of the total number of upper triangular nonzero elements after factorization is assumed to grow as n^1+γ. The expected computational effort for the factorization itself is shown to grow as n^1+2γ, while the one for each repeat solution is shown to grow as n^1+γ. Values of γ for typical power systems are experimentally determined by generating a variety of random networks and ordering the resultant matrices according to "scheme 2". For typical power systems a reasonable value for γ is 0.2. Therefore, methods requiring repeated refactorization of A (such as Newton's method) can be expected to increase as n^1.4, while methods requiring merely repeat solutions (such as fast decoupled methods) can be expected to increase as n^1.2. Several other important comparisons are included.