Fast Graph Matrix Partitioning Algorithm for Solving the Water Distribution System Equations

Abstract

In this paper a method that determines the steady-state hydraulics of a water distribution system, the graph matrix partitioning algorithm (GMPA), is presented. This method extends the technique of separating the linear and nonlinear parts of the problem and using the more time-consuming nonlinear solver only on the nonlinear parts of the problem and faster linear techniques on the linear parts of the problem. The previously developed forest-core partitioning algorithm (FCPA) used this approach to separate the network graph’s external forest from its looped core but did not address the fact that within the core of a network graph there may be many internal trees—nodes in series—for which a more economical linear process can be used. This extension of the separation process can significantly reduce the dimension of the nonlinear problem that must be solved: GMPA applied to eight case study networks with between 900 and 20,000 pipes show reductions to between 5 and 55% of the core dimension (after FCPA). The separation of the problem into its nonlinear and linear parts involves no approximations, such as lumping or skeletonization, and the resulting solution is precisely the solution that would have been obtained by the slower technique of solving the entire network with a nonlinear solver. The new method is applied after the network has been separated into an external forest and core by the FCPA method. GMPA identifies all the nodes in the core that are in series (the internal forest) and then iterates alternately on the remaining core [the (nonlinear) global step] and the internal forest [the (linear) local step]. In this paper, it is formally shown that the smaller set of nonlinear equations in GMPA corresponds to the network equations of a particular topological subgraph of the original graph. Using algebraic manipulations, the size of the linearized system to be solved is reduced to the number of nodes in the core having degrees greater than two. For pipe models of real-world applications that are derived from geographic information system datasets, this can mean a dramatic reduction of the size of the nonlinear problem that has to be solved. The main contributions of the paper are (1) the derivation and presentation of formal proofs for the new method, and (2) demonstrating how significant the reduction in the dimension of the nonlinear problem can be for suitable networks. The method is illustrated by a simple example.