Graph Partitioning in the Analysis of Pressure Dependent Water Distribution Systems
Publication: Journal of Water Resources Planning and Management
Volume 144, Issue 4
Abstract
The forest core partitioning algorithm (FCPA) and the fast graph matrix partitioning algorithm (GMPA) have been used to improve efficiency in the determination of the steady-state heads and flows of water distribution systems that have large, complex network graphs. In this paper, a single framework for the FCPA and the GMPA is used to extend their application from demand dependent models to pressure dependent models (PDMs). The PDM topological minor (TM) is characterized, important properties of its key matrices are identified, and efficient evaluation schemes for the key matrices are presented. The TM captures the network’s most important characteristics: It has exactly the same number of loops as the full network, and the flows and heads of those elements not in the TM depend linearly on those of the TM. The inverse of the TM’s Schur complement is shown to be the top, left block of the inverse of the full system Jacobian’s Schur complement, thereby providing information about the system’s essential behavior more economically than is otherwise possible. The new results are applicable to other nonlinear network problems, such as in gas, district heating, and electrical distribution.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The work presented in the paper was supported in part by the French-German collaborative research project ResiWater that is funded by the French National Research Agency (ANR; project: ANR-14-PICS-0003) and the German Federal Ministry of Education and Research (BMBF; project: BMBF-13N13690).
References
Birkhoff, G. (1963). “A variational principle for nonlinear networks.” Q. Appl. Math., 21(2), 160–162.
Boccaletti, S., Latora, V., Morenod, Y., Chavezf, M., and Hwanga, D.-U. (2006). “Complex networks: Structure and dynamics.” Phys. Rep., 424(4–5), 175–308.
Chiplunkar, A., Mehndiratta, S., and Khanna, P. (1990). “Analysis of looped water distribution networks.” Environ. Software, 5(4), 202–206.
Crous, P., van Zyl, J., and Roodt, Y. (2012). “The potential of graphical processing units to solve hydraulic network equations.” J. Hydroinf., 14(3), 603–612.
Deuerlein, J. (2006). “Efficient supply network management based on linear graph theory.” Water Distribution Systems Analysis Symp. 2006, ASCE, Reston, VA, 1–18.
Deuerlein, J. (2008). “Decomposition model of a general water supply network graph.” J. Hydraul. Eng., 822–832.
Deuerlein, J., Elhay, S., and Simpson, A. (2016). “Fast graph matrix partitioning algorithm for solving the water distribution system equations.” J. Water Resour. Plann. Manage., 04015037.
Deuerlein, J., Piller, O., Elhay, S., and Simpson, A. (2017). “Sensitivity analysis of topological subgraph of water distribution networks.” Procedia Engineering, 186 252–260.
Deuerlein, J., Piller, O., and Montalvo, I. (2014). “Improved real-time monitoring and control of water supply networks by use of graph decomposition.” Procedia Eng., 89, 1276–1281.
Diao, K., Wang, Z., Burger, G., Chen, C., Rauch, W., and Zhou, Y. (2014). “Speedup of water distribution simulation by domain decomposition.” Environ. Modell. Software, 52, 253–263.
Diestel, R. (2010). Graph theory, Vol. 173, 4th Ed., Springer, Heidelberg, Germany.
Di Nardo, A., Di Natale, M., Giudicianni, C., Greco, R., and Santonastaso, G. F. (2017). “Water supply network partitioning based on weighted spectral clustering.” Int. Workshop on Complex Networks and their Applications, Cherifi, H., Gaito, S., Quattrociocchi, W., and Sala, A., eds., Springer, Cham, Switzerland.
Dolan, A., and Aldous, J. (1993). Networks and algorithms: An introductory approach, Wiley, Chichester, U.K.
Elhay, S., Piller, O., Deuerlein, J., and Simpson, A. (2016). “A robust, rapidly convergent method that solves the water distribution equations for pressure dependent models.” J. Water Resour. Plann. Manage., 04015047.
Elhay, S., Simpson, A., Deuerlein, J., Alexander, B., and Schilders, W. (2014). “A reformulated co-tree flows method competitive with the Global Gradient Algorithm for solving the water distribution system equations.” J. Water Resour. Plann. Manage., 04014040.
Estrada, E. (2006). “Network robustness to targeted attacks: The interplay of expansibility and degree distribution.” Eur. Phys. J. B-Condens. Matter Complex Syst, 52(4), 563–574.
Giustolisi, O., and Laucelli, D. (2011). “Water distribution network pressure-driven analysis using the enhanced global gradient algorithm (EGGA).” J. Water Resour. Plann. Manage., 498–510.
Giustolisi, O., Savic, D., Laucelli, D., and Berardi, L. (2011). “Testing linear solvers for WDN models.” Urban Water Management: Challenges and Oppurtunities—11th Int. Conf. on Computing and Control for the Water Industry, Vol. 3, Univ. of Exeter, Exeter, U.K.
Guidolin, M., Savic, D., and Kapelan, Z. (2011). “Computational performance analysis and improvement of the demand-driven hydraulic solver for the CWSNet library.” Computing and Control for the Water Industry 2011, Univ. of Exeter, Exeter, U.K, 1, 45–50.
Herrera, H., Canu, S., Karatzoglou, A., Prez-Garca, R., and Izquierdo, J. (2010). “An approach to water supply clusters by semi-supervised learning.” Proc., Int. Environmental Modelling and Software Society, Swayne, D. A., Yang, W., Voinov, A., Rizzoli, A., and Filatova, T., eds., Ottawa, ON, Canada.
Lan, F., Lin, W., and Lansey, K. (2015). “Scenario-based robust optimization of a water supply system under risk of facility failure.” Environ. Modell. Software, 67, 160–172.
Laucelli, D., Berardi, L., and Giustolisi, O. (2012). “Assessing climate change and asset deterioration impacts on water distribution networks: Demand-driven or pressure-driven network modeling?” Environ. Model. Software, 37, 206–216.
MATLAB [Computer software]. MathWorks, Natick, MA.
Perelman, L., and Ostfeld, A. (2011). “Topological clustering for water distribution systems analysis.” Environ. Modell. Software, 26(7), 969–972.
Perelman, L. S., Allen, M., Preis, A., Iqbal, M., and Whittle, A. (2015). “Automated sub-zoning of water distribution systems.” Environ. Model. Software, 65, 1–14.
Piller, O., Elhay, S., Deuerlein, J., and Simpson, A. (2016). “Local sensitivity of pressure dependent modeling and demand dependent modeling steady-state solutions to variations in parameters.” J. Water Resour. Plann. Manage., 04016074.
Piller, O., Le Fichant, M., and van Zyl, J. (2012). “Lessons learned from restructuring a hydraulic solver for parallel computing.” WDSA 2012: 14th Water Distribution Systems Analysis Conf., Engineers Australia, Adelaide, South Australia, 398–406.
Puust, R., Maddison, M., and Laanearu, J. (2011). “Reviewing the effectiveness of GPU power when used for water network optimization problems.” 11th Int. Computing and Control for the Water Industry 2011, Univ. of Exeter, Exeter, U.K.
Reca, J., and Martinez, J. (2006). “Genetic algorithms for the design of looped irrigation water distribution networks.” Water Resour. Res., 42(W05416), 1–9.
ResiWater. (2017). “Resiwater: Innovative secure sensor networks and model-based assessment tools for increased resilience of water infrastructures.” ⟨http://www.resiwater.eu/project/⟩ (Nov. 20, 2017).
Schilders, W. (2009). “Solution of indefinite linear systems using an LQ decomposition for the linear constraints.” Linear Algebra Appl., 431(3–4), 381–395.
Simpson, A., Elhay, S., and Alexander, B. (2014). “Forest-core partitioning algorithm for speeding up the analysis of water distribution systems.” J. Water Resour. Plann. Manage., 435–443.
Todini, E., and Pilati, S. (1988). A gradient algorithm for the analysis of pipe networks, Wiley, London, 1–20.
Tzatchkov, V. G., Alcocer-Yamanaka, V. H., and Rodriguez-Varela, J. M. (2006). “Water distribution network sectorization projects in Mexican cities along the border with USA.” Proc., 3rd Int. Symp. on Transboundary Water Management, Ciudad Real, Spain, 1–13.
van Zyl, J., Savic, D., and Walters, G. (2006). “Explicit integration method for extended-period simulation of water distribution systems.” J. Hydraul. Eng., 385–392.
Wu, Z., and Lee, I. (2011). “Lessons for parallelizing linear equation solvers and water distribution analysis.” Urban Water Management: Challenges and Opportunities, Centre for Water Systems, Univ. of Exeter, Devon, U.K., 21–26.
Yazdani, A., Otoo, R., and Jeffrey, P. (2011). “Resilience enhancing expansion strategies for water distribution systems: A network theory approach.” Environ. Modell. Software, 26(12), 1574–1582.
Zecchin, A., Thum, P., Simpson, A., and Tischendorf, C. (2012). “Steady-state behavior of large water distribution systems: Algebraic multigrid method for the fast solution of the linear step.” J. Water Resour. Plann. Manage., 639–650.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 144 • Issue 4 • April 2018
Copyright
©2018 American Society of Civil Engineers.
History
Received: Mar 7, 2017
Accepted: Aug 24, 2017
Published online: Feb 8, 2018
Published in print: Apr 1, 2018
Discussion open until: Jul 8, 2018
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.