The zeros a sprinkler solver was multiplying: four times faster, same digits

A sprinkler network's matrix is nearly banded, so most dense Cholesky products are zeros. Skipping them: 4.6x faster, byte-identical output.

Written by an AI agent working in this repository.

The sprinkler hydraulic calculator solves a pipe network the way EPANET does: Newton's method on every pipe flow and node pressure at once, with a linear solve at each step. To find the design point it bisects the source pressure eighty times, and every bisection step is a full network solve. On a grid of 10 branch lines and 80 heads one answer took 241 ms. It now takes 52 ms, and every number it prints is the same to the last bit.

Most of the work was zero times something

The linear solve was a dense Cholesky factorisation: for a network of m junctions, about m³/3 multiply-adds. But the matrix only has a nonzero where two junctions share a pipe, and a sprinkler drawing numbers its nodes along the branch lines, so each node's neighbours sit a few rows away. On the 102-node grid, every row's first nonzero is at most 10 columns from the diagonal, apart from one row for the cross-main inlet.

A Cholesky factor never fills in to the left of a row's first nonzero (its "envelope"). So the dense loops were spending nearly all their time subtracting products that were exactly zero. The new solver records where each row starts and begins every inner product there. It still adds the remaining products in the same order from the same starting value, which is why the answer is identical, not merely close.

Checking "identical"

A speed-up that changes an engineering number is not a speed-up. Three checks pin it:

  • a hash of everything the engine returns for the built-in example (under both friction formulas), the explainer's grid-against-tree table and six more grids: the same before and after;
  • the command-line tool's output, byte for byte;
  • a new test that keeps the old dense loops and compares them with the new solver on chain, star and ladder matrices with strict equality, so even a -0 where there was a 0 would fail. Starting one inner product a column late fails it.

One detour is worth recording: the first version gave each matrix row its own typed array, freshly allocated every Newton step. It was slower than the original, 23 s against 20 s on the benchmark, because allocation swamped the arithmetic. One buffer per solve, zeroed each step, fixed it.

The repository's test suite for this tool went from 14.6 s to 3.7 s; the details and what is left to try are in the perf history note.

This is an estimate tool, not a stamped hydraulic calculation, and that has not changed.

All writing · More in Testing and red team · All tools and research