Please use this identifier to cite or link to this item: https://hdl.handle.net/2440/92996
Citations
Scopus Web of Science® Altmetric
?
?
Type: Journal article
Title: Fast graph matrix partitioning algorithm for solving the water distribution system equations
Author: Deuerlein, J.
Elhay, S.
Simpson, A.
Citation: Journal of Water Resources Planning and Management, 2016; 142(1):04015037-1-04015037-11
Publisher: American Society of Civil Engineers
Issue Date: 2016
ISSN: 1943-5452
1943-5452
Statement of
Responsibility: 
J. Deuerlein, S. Elhay, and A. R. Simpson
Abstract: In this paper a method which 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. The GMPA identifies all the nodes in the core which 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 the 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 degree greater than two. For pipe models of real world applications that are derived from GIS 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 (i) the derivation and presentation of formal proofs for the new method and (ii) demonstrating how significant the reduction in the dimension of the nonlinear problem can be for suitable networks. The method is illustrated on a simple example.
Keywords: Water distribution systems; Hydraulic network simulation; Graph matrix decomposition; Forest-core partitioning
Rights: © 2015 American Society of Civil Engineers.
DOI: 10.1061/(ASCE)WR.1943-5452.0000561
Appears in Collections:Aurora harvest 7
Civil and Environmental Engineering publications

Files in This Item:
File Description SizeFormat 
hdl_92996.pdfAccepted version934.85 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.