Sparse null space algorithms for hydraulic analysis of large-scale water supply networks

Edo Abraham, Ivan Stoianov

Research output: Contribution to journalArticleScientificpeer-review

20 Citations (Scopus)


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 partialupdate 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.

Original languageEnglish
Article number04015058
JournalJournal of Hydraulic Engineering (Reston)
Issue number3
Publication statusPublished - 1 Mar 2016
Externally publishedYes


  • Graph theory
  • Hydraulic analysis
  • Inexact newton method
  • Null space algorithm
  • Partial updates
  • Sparse cholesky
  • Sparse lu
  • Sparse solver
  • Water distribution networks

Fingerprint Dive into the research topics of 'Sparse null space algorithms for hydraulic analysis of large-scale water supply networks'. Together they form a unique fingerprint.

Cite this