NLF: A Resistor-Network Framework and Linear-Time Solver for Convex Network-Flow Equilibria

We present NLF (Nonlinear Laplacian Flow), a unified framework and linear-time solver for convex network-flow equilibria.

Congestion routing, minimum-delay routing, and maximum flow share one form: the nonlinear graph Laplacian $B\rho(B^T\phi)=\alpha d$, where a monotone edge law $\rho_e$ encodes the physics (undirected graphs; directed variants are future work).

NLF solves it by a damped chord-Newton iteration whose frozen linearization -- a weighted graph Laplacian -- is inverted by a near-linear Laplacian solver (default: approximate Cholesky, LAMG+ interchangeable).

The nonlinear solve costs $2$--$4$ linear Laplacian solves, making the wall-clock empirically $O(m)$ in the edge count $m$ (not a proved bound).

On single-commodity congestion (BPR cost), NLF converges on all 2,003 SuiteSparse corpus graphs up to $1.8\times10^7$ edges.

Against a state-of-the-art interior-point method, NLF is a median $2.6\times$ faster where both converge and $>45\times$ on poorly-separable graphs where the IPM's direct core is superlinear; against L-BFGS, a median $4.2\times$ faster and the only solver to finish on the 90 hardest instances.

A multicommodity extension routes $K$ commodities through one shared hierarchy at $O(Km)$ per step.

The same machinery recovers the exact max-flow as a short sequence of Laplacian solves, with the cut potential as a by-product.

Code: this https URL