Sparse Null Space Algorithms for Hydraulic Analysis of Large-Scale Water Supply Networks
Publication: Journal of Hydraulic Engineering
Volume 142, Issue 3
Abstract
In this article, a comprehensive review of existing methods is presented and computationally efficient sparse null space algorithms are proposed for the hydraulic analysis of water distribution networks. The linear systems at each iteration of the Newton method for nonlinear equations are solved using a null space algorithm. The sparsity structure of these linear equations, which arises from the sparse network connectivity, is exploited to reduce computations. A significant fraction of the total flops in the Newton method are spent in computing pipe head losses and matrix-matrix multiplications involving flows. Because most flows converge after a few iterations, a novel partial update of head losses and matrix products is used to further reduce computational complexity. Convergence analyses are also presented for the partial-update formulas. A new heuristic for reducing the number of pressure head computations of a null space method is proposed. These savings enable fast near-real-time control of large-scale water networks. It is often observed that the linear equations that arise in solving the hydraulic equations become ill-conditioned due to hydraulic solutions with very small and zero flows. The condition numbers of the Newton equations are bounded using a regularization technique with insignificant computational overheads. The convergence properties of all proposed algorithms are analyzed by posing them as an inexact-Newton method. Small-scale to large-scale models of operational water networks are used to evaluate the proposed algorithms.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This work was supported by the NEC-Imperial “Big Data Technologies for Smart Water Networks” project.
References
Benzi, M., Golub, G. H., and Liesen, J. (2005). “Numerical solution of saddle point problems.” Acta Numerica, 14(1), 1–137.
Berghout, B. L., and Kuczera, G. (1997). “Network linear programming as pipe network hydraulic analysis tool.” J. Hydraul. Eng., 549–559.
Bhave, P. R. (1988). “Calibrating water distribution network models.” J. Environ. Eng., 120–136.
Boyd, S. P., and Vandenberghe, L. (2004). Convex optimization, Cambridge University Press, Cambridge, U.K.
Brunone, B., et al., eds. (2013). “Informatics for water systems and smart cities.” 12th Int. Conf. on Computing and Control for the Water Industry, CCWI2013, Informatics for Water Systems and Smart Cities, Univ. of Perugia, Perugia, Italy.
Collins, M., Cooper, L., Helgason, R., Kennington, J., and LeBlanc, L. (1978). “Solving the pipe network analysis problem using optimization techniques.” Manage. Sci., 24(7), 747–760.
Creaco, E., and Franchini, M. (2013). “Comparison of Newton-Raphson global and loop algorithms for water distribution network resolution.” J. Hydraul. Eng., 313–321.
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.
Davis, T. A. (2004). “Algorithm 832: Umfpack v4. 3—An unsymmetric-pattern multifrontal method.” ACM Trans. Math. Software, 30(2), 196–199.
Davis, T. A. (2006). Direct methods for sparse linear systems, Vol. 2, Society for Industrial and Applied Mathematics, Philadelphia.
Davis, T. A., and Duff, I. S. (1997). “An unsymmetric-pattern multifrontal method for sparse lu factorization.” SIAM J. Matrix Anal. Appl., 18(1), 140–158.
Dembo, R. S., Eisenstat, S. C., and Steihaug, T. (1982). “Inexact Newton methods.” SIAM J. Numer. Anal., 19(2), 400–408.
Dennis, J. E., Jr., and Schnabel, R. B. (1996). Numerical methods for unconstrained optimization and nonlinear equations, Vol. 16, Society for Industrial and Applied Mathematics, Philadelphia.
Eck, B., and Mevissen, M. (2013). “Fast non-linear optimization for design problems on water networks.” World Environmental and Water Resources Congress 2013, ASCE, Reston, VA, 696–705.
Elhay, S., and Simpson, A. R. (2011). “Dealing with zero flows in solving the nonlinear equations for water distribution systems.” J. Hydraul. Eng., 1216–1224.
Elhay, S., Simpson, A. R., 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.
EPANET version 2.0 [Computer software]. U.S. Environmental Protection Agency, Washington, DC.
Eriksson, K., Estep, D., and Johnson, C. (2004). Applied mathematics: Body and soul: Volume 1: Derivatives and geometry in IR3, Vol. 1, Springer Science & Business Media, Berlin, Heidelberg.
Giustolisi, O., Laucelli, D., Berardi, L., and Savić, D. A. (2011). “Computationally efficient modeling method for large water network analysis.” J. Hydraul. Eng., 313–326.
Giustolisi, O., and Moosavian, N. (2014). “Testing linear solvers for global gradient algorithm.” J. Hydroinf, 16(5), 1178–1193.
Giustolisi, O., Savic, D., and Kapelan, Z. (2008). “Pressure-driven demand and leakage simulation for water distribution networks.” J. Hydraul. Eng., 626–635.
Giustolisi, O., and Walski, T. (2011). “Demand components in water distribution network analysis.” J. Water Resour. Plann. Manage., 356–367.
Golub, G. H., and Van Loan, C. F. (1996). Matrix computations, 3rd Ed., John Hopkins University Press, Baltimore, London.
Gorev, N. B., Kodzhespirov, I. F., Kovalenko, Y., Prokhorov, E., and Trapaga, G. (2012). “Method to cope with zero flows in Newton solvers for water distribution systems.” J. Hydraul. Eng., 456–459.
Guidolin, M., Burovskiy, P., Kapelan, Z., and Savić, D. (2010). “Cwsnet: An object-oriented toolkit for water distribution system simulations.” WDSA 2010 Conf., ASCE, Reston, VA.
Guidolin, M., Kapelan, Z., and Savić, D. (2013). “Using high performance techniques to accelerate demand-driven hydraulic solvers.” J. Hydroinf., 15(1), 38–54.
Higham, N. J. (1996). Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics, Philadelphia.
Jankovic-Nisic, B., and Chan, A. (2013). “London strategic model.” 〈http://www.waterprojectsonline.com〉 (May 3, 2014).
Kelley, C. T. (2003). Solving nonlinear equations with Newton’s method, Vol. 1, Society for Industrial and Applied Mathematics, Philadelphia.
Kovalenko, Y., and Prokhorov, E. (2013). “Discussion of dealing with zero flows in solving the nonlinear equations for water distribution systems by Sylvan Elhay and Angus R. Simpson.” J. Hydraul. Eng., 557–558.
Mair, M., Sitzenfrei, R., Kleidorfer, M., and Rauch, W. (2014). “Performance improvement with parallel numerical model simulations in the field of urban water management.” J. Hydroinf., 16(2), 477–486.
MATLAB version 8.2. 0.701 [Computer software]. MathWorks, Natick, MA.
Mays, L. W. (2000). Water distribution systems handbook, McGraw-Hill, New York, London.
Nicolini, M., and Zovatto, L. (2009). “Optimal location and control of pressure reducing valves in water networks.” J. Water Resour. Plann. Manage., 178–187.
Nielsen, H. B. (1989). “Methods for analyzing pipe networks.” J. Hydraul. Eng., 139–157.
Nocedal, J., and Wright, S. J. (2006). Numerical optimization, Springer, New York.
Ostfeld, A., et al. (2008). “The battle of the water sensor networks (BWSN): A design challenge for engineers and algorithms.” J. Water Resour. Plann. Manage., 556–568.
Pearson, J. W., Stoll, M., and Wathen, A. J. (2012). “Regularization-robust preconditioners for time-dependent PDE-constrained optimization problems.” SIAM J. Matrix Anal. Appl., 33(4), 1126–1152.
Pearson, J. W., and Wathen, A. J. (2012). “A new approximation of the Schur complement in preconditioners for PDE-constrained optimization.” Numer. Linear Algebra Appl., 19(5), 816–829.
Rahal, H. (1995). “A co-tree flows formulation for steady state in water distribution networks.” Adv. Eng. Software, 22(3), 169–178.
Rossman, L. A. (2000). EPANET 2: Users manual, Water Supply and Water Resources Division, Cincinnati.
Savic, D. A., and Walters, G. A. (1997). “Genetic algorithms for least-cost design of water distribution networks.” J. Water Resour. Plann. Manage., 67–77.
Sensus. (2012). “White paper: Water 20/20, bringing smart water networks into focus.” SENSUS, Raleigh, NC.
Simpson, A., and Elhay, S. (2010). “Jacobian matrix for solving water distribution system equations with the Darcy-Weisbach head-loss model.” J. Hydraul. Eng., 696–700.
SuiteSparse version 4.1.2 [Computer software]. Texas A&M Univ., TX.
Todini, E., and Pilati, S. (1988). “A gradient algorithm for the analysis of pipe networks.” Computer application in water supply, Vol. I—System analysis and simulation, B. Coulbeck and O. Choun-Hou, eds., Wiley, London, 1–20.
Todini, E., and Rossman, L. A. (2012). “Unified framework for deriving simultaneous equation algorithms for water distribution networks.” J. Hydraul. Eng., 511–526.
Wright, R., Stoianov, I., Parpas, P., Henderson, K., and King, J. (2014). “Adaptive water distribution networks with dynamically reconfigurable topology.” J. Hydroinf, 16(6), 1280–1301.
Zecchin, A. C., Thum, P., Simpson, A. R., 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 Hydraulic Engineering
Volume 142 • Issue 3 • March 2016
Copyright
© 2015 American Society of Civil Engineers.
History
Received: Aug 1, 2014
Accepted: Aug 3, 2015
Published online: Oct 15, 2015
Published in print: Mar 1, 2016
Discussion open until: Mar 15, 2016
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.