Bridge-Block Partitioning Algorithm for Speeding Up Analysis of Water Distribution Systems
Publication: Journal of Water Resources Planning and Management
Volume 145, Issue 9
Abstract
Many water distribution system (WDS) solution methods have been developed to perform demand-driven steady-state analysis. These methods are used to solve the nonlinear system of equations that model a WDS. WDS networks have structural properties that can often be exploited to speed up these solution methods. One solution method that exploits these structural properties is the forest-core partitioning algorithm that was proposed as a preprocessing and postprocessing method that can be used to separate the network into a linear forest component and a nonlinear core component. This paper presents a complementary method for preprocessing and postprocessing called the bridge-block partitioning algorithm (BBPA). This method further partitions the core component of the network into a number of linear bridge components and a number of nonlinear block components. The use of BBPA to partition a WDS network provides significant advantages over current solution methods in terms of both speed and solution reliability.
Get full access to this article
View all available purchase options and get full access to this article.
References
Abraham, E., and I. Stoianov. 2016. “Sparse null space algorithms for hydraulic analysis of large-scale water supply networks.” J. Hydraul. Eng. 142 (3): 04015058. https://doi.org/10.1061/(ASCE)HY.1943-7900.0001089.
Alvarruiz, F., F. Martínez-Alzamora, and A. Vidal. 2015. “Improving the efficiency of the loop method for the simulation of water distribution systems.” J. Water Resour. Plann. Manage. 141 (10): 04015019. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000539.
Benzi, M., G. Golub, and J. Liesen. 2005. “Numerical solution of saddle point problems.” Acta. Num. 14: 1–137. https://doi.org/10.1017/S0962492904000212.
Creaco, E., and M. Franchini. 2013. “Comparison of Newton-Raphson global and loop algorithms for water distribution network resolution.” J. Hydraul. Eng. 140 (3): 313–321. https://doi.org/10.1061/(ASCE)HY.1943-7900.0000825.
Cross, H. 1936. Analysis of flow in networks of conduits or conductors. Urbana, IL: Univ. of Illinois.
Deuerlein, J., S. Elhay, and A. R. Simpson. 2015. “Fast graph matrix partitioning algorithm for solving the water distribution system equations.” J. Water Resour. Plann. Manage. 142 (1): 04015037. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000561.
Deuerlein, J. W. 2008. “Decomposition model of a general water supply network graph.” J. Hydraul. Eng. 134 (6): 822–832. https://doi.org/10.1061/(ASCE)0733-9429(2008)134:6(822).
Diestel, R. 2005. “Graph theory.” Graduate Texts in Mathematics, 173. Berlin: Springer.
Elhay, S., and A. R. Simpson. 2011. “Dealing with zero flows in solving the nonlinear equations for water distribution systems.” J. Hydraul. Eng. 137 (10): 1216–1224. https://doi.org/10.1061/(ASCE)HY.1943-7900.0000411.
Elhay, S., A. R. Simpson, J. Deuerlein, B. Alexander, and W. H. Schilders. 2014. “Reformulated co-tree flows method competitive with the global gradient algorithm for solving water distribution system equations.” J. Water Resour. Plann. Manage. 140 (12): 04014040. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000431.
Epp, R., and A. G. Fowler. 1970. “Efficient code for steady-state flows in networks.” J. Hydraul. Div. 96 (1): 43–56.
Hopcroft, J., and R. Tarjan. 1973. “Algorithm 447: Efficient algorithms for graph manipulation.” Commun. ACM 16 (6): 372–378. https://doi.org/10.1145/362248.362272.
IEEE. 1985. IEEE standard for binary floating-point arithmetic. ANSI/IEEE 754. New York: IEEE.
Schilders, W. H. 2009. “Solution of indefinite linear systems using an LQ decomposition for the linear constraints.” Linear Algebra Appl. 431 (3): 381–395. https://doi.org/10.1016/j.laa.2009.02.036.
Simpson, A. R., and S. Elhay. 2010. “Jacobian matrix for solving water distribution system equations with the Darcy-Weisbach head-loss model.” J. Hydraul. Eng. 137 (6): 696–700. https://doi.org/10.1061/(ASCE)HY.1943-7900.0000341.
Simpson, A. R., S. Elhay, and B. Alexander. 2012. “Forest-core partitioning algorithm for speeding up analysis of water distribution systems.” J. Water Resour. Plann. Manage. 140 (4): 435–443. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000336.
Todini, E., and S. Pilati. 1988. “A gradient algorithm for the analysis of pipe networks.” In Vol. 1 of Computer applications in water supply, 1–20. Letchworth, UK: Research Studies Press.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 145 • Issue 9 • September 2019
Copyright
©2019 American Society of Civil Engineers.
History
Received: May 2, 2018
Accepted: Dec 12, 2018
Published online: Jun 28, 2019
Published in print: Sep 1, 2019
Discussion open until: Nov 28, 2019
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.