Performance Scalability

[ConnorG51]

I have been testing the scalability of PGM vs the likes of Pandapower and PowerFactory, and from my findings PGMs performance time scales linearly as a function of the number of network nodes, as opposed to the others having a trend of n^2.

Am I correct with these results, and could you explain as to why it scales like this?

[mgovers]

Hi @ConnorG51 ,

Thank you for your valuable input. Apologies for our late response. Apparently, there was an issue regarding notifications and we completely missed this discussion.

• For radial grids, our algorithms scale as O(N).
• For meshed grids, however, our algorithms scale as O(N²), but even then, most steps scale O(N). In addition, depending on what and how you benchmark, we may cache the state, meaning that the O(N)-scaling steps usually dominate the calculations for reasonably small N. Only for extremely large amounts of nodes will the quadratic behavior come into play. I do not have exact numbers at the moment for where that transition happens, but we would be very happy if you are able to share your results with us. Inspiration may come from the benchmark done in this PR

I hope this answer and the more extensive one below help you continue your research. Please let me know if there's anything else we can help you with. I'm now subscribed to this discussion, so response should be much faster.

Kind regards,

Martijn

Long answer

In an attempt to give a more elaborate answer, I will break it down as much as I can. We do several optimizations to try and get the scaling as close to optimal as possible. See also performance guide for a quick overview of tips and tricks a user might use to obtain better performance without going into detail. The different types of optimizations involve the different layers of the core design.

Conventions

Let's call N the total amount of components, n the amount of nodes and e the amount of edges (Branch and Branch3 components) and a the amount of non-edge components that connect to nodes (Appliance) and o the amount of components that connect to other components (Sensor and Fault). Therefore, N = n + e + a + o.

Note that:

• for pretty much all practical use cases:
  • e > n > 1
  • a > 1 and a may be a > n or a <= n
• for power flow calculation:
  • o >= 0
• for state estimation:
  • o >= n (see the comment on observability)
• for short circuit calculation:
  • o >= 1

Breakdown

Interfacing

• input step is O(n + e + a + o) on average
• update step is O(N_{update}) on average
  • Depending on the data, in some batch cases, it can be reduced to one single call for the entire batch instead of for every scenario.
• output step is O(N)

Topology

Topology step containing graph optimization depends heavily on the type of network:

• Depth-first search: O(n + E)
• If the graph contains cycles containing at least 4 edges: minimum degree ordering is O(n e + e²/n)
  • this can become an expensive step
  • We are working on some improvements, see also [FEATURE] In-house minimum degree reordering power-grid-model#433 and its follow-ups
• Reorganization of components: O(N)

Ybus construction

O(N)

• Some steps are skipped when updating if the topology doesn't change

Solving

This may depend on the calculation type and solver used. We assuming constant amount of iterations for iterative approaches

• Preparing of the matrix equation: O(N) on average
  • May depend on type of calculation and solver
• LU decomposition: O(e²/n)
  • We make use of the fact that the data is expected to be extremely sparse
  • It relies very heavily on the reorganization of the topology step (depth-first + minimum degree) by means of 'fill-in's (see https://en.wikipedia.org/wiki/Minimum_degree_algorithm)
  • For some solvers, this happens only once as long as the topology does not change
  • For others may be required for every iteration (e.g. Newton-Raphson state estimation, see also its documentation)
• Solving the matrix equation: O(e)

Summary/conclusion

Overall, depending on what your data looks like, which solver you use and whether you benchmark batches or clean runs from scratch, your scaling may be:

• O(n e) if you take the construction of the model into account (meshed grids)
  • (near-)radial grids are significantly faster and may run in O(n + e)
  • Although the complexity will remain the same, hopefully, the construction will become even faster in the future
• O(e² / n) if you do not take the construction into account
• O(n + e) if you choose a fast solver (e.g. linear power flow), do not update topology, do a single calculation first and then benchmark only runs of the power grid model after that. This allows some type of "precalculation"
• For radial grids, the overall performance is O(n + e + e²/n) = O(N)
• For meshed grids, the overall performance is O(n e) = O(N²)

[mgovers]

Hi @ConnorG51 ,

In particular, we use Boost's implementation of minimum degree ordering, which appears to implement AMD and runs in O(ne) but is an approximate solution.

Recent advancements have come up with an exact algorithm that runs in O(n e).

We intend to implement the improved algorithm to obtain the O(n e) complexity I initially claimed, while being optimal in the other parts of the algorithm.

[mgovers]

Hi @ConnorG51 , I found some more nuances to the additions from this morning and updated both the original answer and the comment with the latest information.