Demonstrating Almost Linear Time Complexity of Bus Admittance Matrix-Based Distribution Network Power Flow: An Empirical Approach

The bus admittance matrix is central to many power system simulation algorithms, but the link between problem size and computation time (i.e., the time complexity) using modern sparse solvers is not fully understood. It has recently been suggested that some popular algorithms used in distribution system power flow analysis have cubic complexity, based on properties of dense matrix numerical algorithms; a tighter theoretical estimate of complexity using sparse solvers is not immediately forthcoming due to these solvers' problem-dependent behaviour. To address this, the time complexity of admittance matrix-based distribution power flow is considered empirically across a library of 75 networks, ranging in size from 50 to 300,000 nodes. Results across four admittance matrix-based methods suggest complexity coefficient values between 1.04 and 1.12, indicating complexity that is instead almost linear. The proposed empirical approach is suggested as a convenient and practical way of benchmarking the scalability of power flow algorithms.