Steady-State Behavior of Large Water Distribution Systems: Algebraic Multigrid Method for the Fast Solution of the Linear Step
Publication: Journal of Water Resources Planning and Management
Volume 138, Issue 6
Abstract
The Newton-based global gradient algorithm (GGA) (also known as the Todini and Pilati method) is a widely used method for computing the steady-state solution of the hydraulic variables within a water distribution system (WDS). The Newton-based computation involves solving a linear system of equations arising from the Jacobian of the WDS equations. This step is the most computationally expensive process within the GGA, particularly for large networks involving up to variables. An increasingly popular solver for large linear systems of the M-matrix class is the algebraic multigrid (AMG) method, a hierarchical-based method that uses a sequence of smaller dimensional systems to approximate the original system. This paper studies the application of AMG to the steady-state solution of WDSs through its incorporation as the linear solver within the GGA. The form of the Jacobian within the GGA is proved to be an M-matrix (under specific criteria on the pipe resistance functions), and thus able to be solved using AMG. A new interpretation of the Jacobian from the GGA is derived, enabling physically based interpretations of the AMG’s automatically created hierarchy. Finally, extensive numerical studies are undertaken where it is seen that AMG outperforms the sparse Cholesky method with node reordering (the solver used in EPANET2), incomplete LU factorization (ILU), and PARDISO, which are standard iterative and direct sparse linear solvers.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This research has been financially supported by the Australia-Germany Joint Research Co-operation Scheme cofunded by the Australian Group of Eight and the German Academic Exchange Service (DAAD).
References
Brandt, A., McCormick, S., and Ruge, J. (1984). “Algebraic multigrid (AMG) for sparse matrix equations.” Sparsity and its applications, Evans, D.ed., Cambridge University Press, Cambridge, UK, 257–284.
Chen, W.-K. (1983). Linear networks and systems, Brooks/Cole Engineering Division, Monterey, CA.
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.
Cross, H. (1936). “Analysis of flow in networks of conduits or conductors.” Eng. Exp. Stn. Bull., 286, 329.
Deuerlein, J. W., Simpson, A. R., and Dempe, S. (2009). “Modeling the behavior of flow regulating devices in water distribution systems using constrained nonlinear programming.” J. Hydraul. Eng., 135(11), 970–982.
Elhay, S., and Simpson, A. R. (2011). “Dealing with zero flows in solving the nonlinear equations for water distribution systems.” J. Hydraul. Eng., 137(10), 1216–1224.
Gould, N. I. M., Scott, J. A., and Hu, Y. (2007). “A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations.” Trans. Math. Software, 33(2), 32 pp.
Martin, D. W., and Peters, G. (1963). “The application of Newton’s method to network analysis by digital computer.” J. Inst. Water Eng. Sci., 17, 115–129.
Nielson, H. B. (1989). “Methods for analyzing pipe networks.” J. Hydraul. Eng., 115(2), 139–157.
Piller, O. (1995). “Modeling the behavior of a network—Hydraulic analysis and sampling procedures for parameter estimation.” Ph.D., The Univ. of Bordeaux I Bordeaux, France.
Rossman, L. (2000). “Epanet 2 users manual.”, National Risk Management Research Laboratory Office of Research and Development, U.S. Environmental Protection Agency, Cincinnati, OH.
Saad, Y. (2003). Iterative methods for sparse linear systems, 2nd Ed., Society for Industrial and Applied Mathematics, Philadelphia.
Schenk, O., Gärtner, K., and Fichtner, W. (1999). “Efficient sparse LU factorization with left-right looking strategy on shared memory multiprocessors.” BIT Numer. Math., 40(1), 158–176.
Simpson, A. R., and Elhay, S. (2011). “Jacobian matrix for solving water distribution system equations with the Darcy-Weisbach head-loss model.” J. Hydraul. Eng., 137(6), 696–700.
Streeter, V. L., Wylie, E. B., and Bedford, K. W. (1997). Fluid mechanics, 9th Ed., WCB/McGraw Hill, Boston.
Stüben, K. (1983). “Algebraic multigrid (AMG): Experiences and comparisons.” Appl. Math. Comput., 13(3–4), 419–452.
Stüben, K. (2001a). “A review of algebraic multigrid. A short report on AMG and the basic solver technology.” J. Comput. Appl. Math., 128(1–2), 281–309.
Stüben, K. (2001b). “An introduction to algebraic multigrid.” Multigrid, Trottenberg, U., Oosterlee, C., and Schüller, A., eds., Academic Press, London, 413–532.
Stüben, K., Delaney, P., and Chmakov, S. (2003). “Algebraic multigrid (AMG) for ground water flow and oil reservoir simulation.” Groundwater Modelling Conf. MODFLOW and MORE, Colorado School of Mines, Golden, CO.
Swamee, P. K., and Jain, A. K. (1976). “Explicit equations for pipe-flow problems.” J. Hydraul. Div., 102(5), 657–664, http://cedb.asce.org/cgi/WWWdisplay.cgi?6693.
Todini, E. (2011). “Extending the global gradient algorithm to unsteady flow extended period simulations of water distribution systems.” J. Hydroinf., 13(2), 167–180.
Todini, E., and Pilati, S. (1988). “A gradient algorithm for the analysis of pipe networks.” Computer applications in water supply, Coulbeck, B., and Orr, C. H., eds., Research Studies Press, Letchworth, Hertfordshire, UK, 1–20.
Trottenberg, U., Oosterlee, C., and Schüller, A. (2001). Multigrid, Academic Press, London.
Wu, Z. Y., Wang, R. H., Walski, T. M., Yang, S. Y., Bowdler, D., and Baggett, C. C. (2009). “Extended global-gradient algorithm for pressure-dependent water distribution analysis.” J. Water Resour. Plann. Manage., 135(1), 13–22.
Zecchin, A. C. (2010). “Laplace-domain analysis of fluid line networks with applications to 590 time-domain simulation and system parameter identification.” Ph.D., The School of Civil, Environmental and Mining Engineering, The Univ. of Adelaide, Adelaide, Australia.
Zecchin, A. C., Simpson, A. R., Lambert, M. F., White, L. B., and Vitkovsky, J. P. (2009). “Transient modeling of arbitrary pipe networks by a Laplace-domain admittance matrix.” J. Eng. Mech., 135(6), 538–547.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 138 • Issue 6 • November 2012
Pages: 639 - 650
Copyright
© 2012 American Society of Civil Engineers.
History
Received: Oct 12, 2010
Accepted: Jan 5, 2012
Published online: Jan 7, 2012
Published in print: Nov 1, 2012
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.