Forest-Core Partitioning Algorithm for Speeding Up Analysis of Water Distribution Systems

Abstract

Commonly, water distribution networks have many treed or branched subgraphs. The equations for these systems are often solved for the steady-state flows and heads with a fast implementation of Newton’s method such as the global gradient algorithm (GGA). Applying the GGA to the whole of a network that has a treed portion means using a nonlinear solver on a problem that has separable linear and nonlinear parts. This is not optimal, and the flows and heads of treed networks can be found more quickly if the flows and heads of the treed portions are first solved explicitly by a linear process and then only the flows and heads of the smaller looped part of the network are found using the nonlinear GGA solver. The main contributions in this paper are the following: (1) development of a forest-core partitioning algorithm (FCPA), which separates the linear treed part of the network (the forest) from the nonlinear looped part (the core) by inspecting the incidence matrix; this allows the linear and nonlinear parts of the problem to be solved separately by linear and nonlinear methods, respectively; (2) explaining the mathematical basis for the adjustment of the network as the forest is identified and relating the mathematics to adjusting the graph of the network; (3) demonstration of flop count savings of between approximately 40 and 70% achievable in the linear phase of the GGA with forest-core partitioning on eight realistic case study water distribution networks ranging in size from 932 to 19,647 pipes; these savings lead, in turn, to savings in total CPU times of between 11 and 31% on the same networks; and (4) removing the need to use special techniques to deal with zero flows in forest pipes that have head loss modeled by the Hazen-Williams formulation. Where zero flows occur in the core, as a result of equal heads at the two ends of a pipe, special techniques will still need to be used.