pith. sign in

arxiv: 2607.02041 · v1 · pith:JWG3KEJSnew · submitted 2026-07-02 · 🧮 math.NA · cs.NA

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

Oren E. Livne This is my paper

Pith reviewed 2026-07-03 07:55 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords network flownonlinear LaplacianNewton methodconvex optimizationgraph algorithmscongestion routingmaximum flow
0
0 comments X

The pith

Convex network-flow equilibria reduce to a nonlinear graph Laplacian solved by a few linear Laplacian inversions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces NLF to solve convex network flow problems such as congestion routing and maximum flow by casting them as the nonlinear equation Bρ(B^T φ) = α d on an undirected graph. A damped chord-Newton iteration linearizes this at each step to a weighted graph Laplacian, which is inverted by an existing near-linear solver. The full nonlinear solve requires only two to four such linear solves, producing an empirically linear-time algorithm in the edge count. This approach converges on every graph in a large public corpus and runs faster than interior-point and quasi-Newton baselines, especially on hard instances.

Core claim

The nonlinear graph Laplacian Bρ(B^T φ) = α d with monotone edge law ρ can be solved reliably by a damped chord-Newton iteration that freezes the linearization as a weighted Laplacian and inverts it with a near-linear solver, requiring only 2-4 linear solves total and converging on all tested graphs up to 1.8×10^7 edges.

What carries the argument

The nonlinear graph Laplacian equation Bρ(B^T φ) = α d, where ρ_e is a monotone edge law; the damped chord-Newton iteration freezes its linearization to a weighted graph Laplacian solved by an existing near-linear routine.

If this is right

  • Multicommodity routing of K commodities costs O(Km) per iteration using one shared hierarchy.
  • Exact maximum flow is recovered as a short sequence of the same Laplacian solves, yielding the cut potential as a byproduct.
  • On single-commodity BPR congestion the method finishes every one of the 2003 SuiteSparse graphs up to 18 million edges.
  • Where both converge, the method is a median 2.6 times faster than a state-of-the-art interior-point solver and 4.2 times faster than L-BFGS.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The resistor-network analogy may extend the same linearization technique to other equilibrium problems whose governing laws are monotone but not yet cast as network flows.
  • Because each nonlinear step reuses an off-the-shelf Laplacian solver, further improvements in linear Laplacian algorithms immediately accelerate the nonlinear solver without code changes.
  • The empirical linear scaling suggests that real-time recomputation of equilibria on city-scale or internet-scale graphs becomes feasible if the same convergence behavior holds on dynamic or streaming inputs.

Load-bearing premise

The damped chord-Newton iteration with frozen weighted Laplacian linearization converges reliably for the monotone edge laws that encode the physics of the target problems.

What would settle it

A single undirected graph and monotone edge law on which the iteration diverges or requires more than a small constant number of linear solves would falsify the central performance claim.

Figures

Figures reproduced from arXiv: 2607.02041 by Oren E. Livne.

Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
Figure 5
Figure 5. Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6 [PITH_FULL_IMAGE:figures/full_fig_p020_6.png] view at source ↗
read the original abstract

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: https://github.com/orenlivne/nlf

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper presents the NLF framework for convex network-flow equilibria on undirected graphs, formulated as the nonlinear Laplacian equation B ρ(B^T φ) = α d with monotone edge laws ρ_e. It solves this via a damped chord-Newton iteration that freezes a weighted Laplacian at each step and inverts it with a near-linear solver (e.g., approximate Cholesky), claiming that the nonlinear phase requires only 2–4 linear solves and is therefore empirically O(m) in edge count m. Extensive experiments on single-commodity BPR congestion routing show convergence on all 2,003 SuiteSparse graphs (up to 1.8×10^7 edges), with median speedups of 2.6× over interior-point methods and 4.2× over L-BFGS, plus a multicommodity extension and recovery of exact max-flow.

Significance. If the empirical reliability of the iteration holds across the claimed problem class, NLF would supply a practical, scalable reduction of monotone network equilibria to a handful of Laplacian solves, leveraging existing near-linear solvers. The open-source implementation and exhaustive testing on a large public corpus constitute concrete strengths that would make the contribution immediately usable for congestion routing and related problems.

major comments (2)
  1. [Abstract] Abstract and algorithmic description: the central performance claim—that the nonlinear solve requires only 2–4 linear Laplacian solves, yielding empirical O(m) wall-clock time—rests entirely on the damped chord-Newton iteration with frozen weighted Laplacian converging reliably for the monotone ρ_e arising in the target applications. No convergence theorem, iteration bound, or damping-parameter guarantee is supplied; the manuscript explicitly labels the O(m) statement as unproved. This is load-bearing for all reported speed comparisons and the “linear-time solver” framing.
  2. [Experiments] Experimental section (SuiteSparse corpus): while success on all 2,003 graphs is reported, the manuscript supplies no a-priori criterion for selecting the damping parameter, no characterization of failure modes, and no test on other monotone laws beyond BPR. Without such analysis the reliability claim cannot be extrapolated beyond the specific corpus and cost function examined.
minor comments (2)
  1. [Abstract] The parenthetical qualifier “(not a proved bound)” in the abstract is helpful; the same explicit distinction between empirical observation and theoretical guarantee should appear in the main algorithmic and complexity sections.
  2. [Framework] Notation: the scalar α in the equilibrium equation B ρ(B^T φ) = α d is introduced without an explicit definition of its role relative to the demand vector d; a short clarifying sentence would remove ambiguity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed report and for recognizing the practical strengths of the NLF framework, the exhaustive SuiteSparse experiments, and the open-source release. We address the two major comments below.

read point-by-point responses

  1. Referee: [Abstract] Abstract and algorithmic description: the central performance claim—that the nonlinear solve requires only 2–4 linear Laplacian solves, yielding empirical O(m) wall-clock time—rests entirely on the damped chord-Newton iteration with frozen weighted Laplacian converging reliably for the monotone ρ_e arising in the target applications. No convergence theorem, iteration bound, or damping-parameter guarantee is supplied; the manuscript explicitly labels the O(m) statement as unproved. This is load-bearing for all reported speed comparisons and the “linear-time solver” framing.

    Authors: We agree that the O(m) statement is presented as an empirical observation, not a proved bound, as the manuscript already states. The reported speedups are measured wall-clock times on the tested instances rather than derived from the asymptotic label. The core contribution is the reduction of the nonlinear equilibrium to a small number of calls to an existing near-linear Laplacian solver. We will revise the abstract and the opening of Section 3 to foreground the empirical character of the iteration count and to add a short paragraph summarizing the observed 2–4 iterations across the corpus. A general convergence theorem for arbitrary monotone ρ_e remains an open question outside the scope of the present work. revision: partial

  2. Referee: [Experiments] Experimental section (SuiteSparse corpus): while success on all 2,003 graphs is reported, the manuscript supplies no a-priori criterion for selecting the damping parameter, no characterization of failure modes, and no test on other monotone laws beyond BPR. Without such analysis the reliability claim cannot be extrapolated beyond the specific corpus and cost function examined.

    Authors: The damping schedule is a fixed heuristic (initial damping factor 0.5 with multiplicative reduction) whose details appear in the implementation appendix; we will move this description into the main experimental section and state the criterion explicitly. Because the method succeeded on every graph in the 2,003-graph corpus, no failure modes were observed; we will add a sentence noting this fact and the consequent absence of a failure-mode characterization. The paper centers on the BPR law as the motivating application. We will include one additional experiment with a different monotone law (linear resistance) to illustrate that the same iteration structure applies, while acknowledging that a broader sweep of cost functions lies beyond the current scope. revision: partial

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents NLF as an empirical solver for the convex network-flow equation Bρ(B^T φ)=αd using a damped chord-Newton iteration whose linearizations are handled by existing near-linear Laplacian solvers. All performance claims (2–4 linear solves per nonlinear solve, empirical O(m) wall-clock time, convergence on the full SuiteSparse corpus) are reported as direct experimental observations rather than derived quantities obtained by fitting parameters to the target data or by self-referential definitions. No load-bearing self-citations, uniqueness theorems imported from prior author work, or ansatzes smuggled via citation appear in the provided text; the central claims therefore remain independent of the method’s own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Review based on abstract only; the central claim rests on the assumption of monotone edge laws and the practical convergence of the Newton iteration, both stated without further derivation in the provided text.

axioms (1)
  • domain assumption The edge law ρ_e is monotone for each edge e.
    Invoked to guarantee well-posedness of the nonlinear equation and suitability of the Newton linearization.
invented entities (1)
  • NLF (Nonlinear Laplacian Flow) framework no independent evidence
    purpose: Unified modeling and solution approach for convex network-flow equilibria
    Introduced in the abstract as the paper's core contribution; no independent evidence outside the paper is supplied.

pith-pipeline@v0.9.1-grok · 5831 in / 1465 out tokens · 36726 ms · 2026-07-03T07:55:45.018825+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    O. E. Livne and A. Brandt,Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver, SIAM J. Sci. Comput.34(4), B499–B522, 2012

    2012

  2. [2]

    R. D. Zimmerman, C. E. Murillo-S´ anchez, and R. J. Thomas,MATPOWER: Steady-state operations, planning, and analysis tools for power systems research and education, IEEE Trans. Power Syst.26(1), 12–19, 2011

    2011

  3. [3]

    Coffrin, R

    C. Coffrin, R. Bent, K. Sundar, Y. Ng, and M. Lubin,PowerModels.jl: an open-source frame- work for exploring power flow formulations, Power Systems Computation Conf. (PSCC), 2018. 24O. E. LIVNE

    2018

  4. [4]

    DOE ARPA-E,Grid Optimization (GO) Competition, 2019–2023; https://gocompetition.energy.gov

    U.S. DOE ARPA-E,Grid Optimization (GO) Competition, 2019–2023; https://gocompetition.energy.gov

    2019

  5. [5]

    D. A. Spielman and S.-H. Teng,Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, SIAM J. Comput.40(4), 981–1025, 2011

    2011

  6. [6]

    Koutis, G

    I. Koutis, G. L. Miller, and D. Tolliver,Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing, Comput. Vis. Image Underst.115(12), 1638–1646, 2011

    2011

  7. [7]

    Ponce, D

    C. Ponce, D. S. Bindel, and P. S. Vassilevski,A nonlinear algebraic multigrid framework for the power flow equations, SIAM J. Sci. Comput.40(3), B812–B833, 2018

    2018

  8. [8]

    O. E. Livne,LAMG+: A Robust Lean Algebraic Multigrid Solver for Graph Laplacians, arXiv:2606.24791, 2026; code at https://github.com/orenlivne/lamgplus

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  9. [9]

    Beckmann, C

    M. Beckmann, C. B. McGuire, and C. B. Winsten,Studies in the Economics of Transportation, Yale Univ. Press, 1956 (traffic equilibrium)

    1956

  10. [10]

    Bureau of Public Roads,Traffic Assignment Manual, U.S. Dept. of Commerce, Urban Planning Division, 1964

    1964

  11. [11]

    S. D. Boyles, N. E. Lownes, and A. Unnikrishnan,Transportation Network Analy- sis, Volume I: Static and Dynamic Traffic Assignment, 2nd ed., open textbook, sboyles.github.io/blubook.html, 2023 (modern treatment of Beckmann–Wardrop equi- librium and its algorithms)

    2023

  12. [12]

    Transportation Networks for Research Core Team,Transportation Networks for Research, github.com/bstabler/TransportationNetworks(accessed 2026)

    2026

  13. [13]

    Frank and P

    M. Frank and P. Wolfe,An algorithm for quadratic programming, Naval Res. Logist. Quart. 3(1–2), 1956

    1956

  14. [14]

    W¨ achter and L

    A. W¨ achter and L. T. Biegler,On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program.106(1), 2006 (Ipopt)

    2006

  15. [15]

    Bertsekas and R

    D. Bertsekas and R. Gallager,Data Networks, 2nd ed., Prentice Hall, 1992 (minimum-delay routing, Kleinrock cost)

    1992

  16. [16]

    Mendiola, J

    A. Mendiola, J. Astorga, E. Jacob, and M. Higuero,A survey on the contributions of software- defined networking to traffic engineering, IEEE Commun. Surveys Tuts.19(2), 918–953, 2017 (modern survey of delay/utilization-driven routing optimization)

    2017

  17. [17]

    R. K. Ahuja, T. L. Magnanti, and J. B. Orlin,Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993

    1993

  18. [18]

    A. V. Goldberg and R. E. Tarjan,A new approach to the maximum-flow problem, J. ACM 35(4), 1988 (push–relabel)

    1988

  19. [19]

    A. V. Goldberg and R. E. Tarjan,Efficient maximum flow algorithms, Commun. ACM57(8), 82–89, 2014 (survey)

    2014

  20. [20]

    L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. Probst Gutenberg, and S. Sachdeva,Maximum flow and minimum-cost flow in almost-linear time, Proc. 63rd IEEE Symp. Foundations of Computer Science (FOCS), 612–623, 2022

    2022

  21. [21]

    Boykov and V

    Y. Boykov and V. Kolmogorov,An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision, IEEE TPAMI26(9), 2004

    2004

  22. [22]

    D. S. Johnson and C. C. McGeoch (eds.),Network Flows and Matching: First DIMACS Im- plementation Challenge, AMS, 1993 (genrmf,washington)

    1993

  23. [23]

    Christiano, J

    P. Christiano, J. A. Kelner, A. Madry, D. A. Spielman, and S.-H. Teng,Electrical flows, Laplacian systems, and faster approximate maximum flow, STOC, 2011

    2011

  24. [24]

    S. I. Daitch and D. A. Spielman,Faster approximate lossy generalized flow via interior point algorithms, STOC, 2008

    2008

  25. [25]

    Kyng and S

    R. Kyng and S. Sachdeva,Approximate Gaussian elimination for Laplacians—fast, sparse, and simple, FOCS, 2016 (approxChol, implemented inLaplacians.jl)

    2016

  26. [26]

    P. G. Doyle and J. L. Snell,Random Walks and Electric Networks, Mathematical Association of America, 1984

    1984

  27. [27]

    H. B. Keller,Numerical solution of bifurcation and nonlinear eigenvalue problems, inApplica- tions of Bifurcation Theory, Academic Press, 1977 (pseudo-arclength)

    1977

  28. [28]

    E. L. Allgower and K. Georg,Introduction to Numerical Continuation Methods, SIAM Classics in Applied Mathematics45, 2003

    2003

  29. [29]

    S. G. Nash,A multigrid approach to discretized optimization problems, Optim. Methods Softw. 14(1–2), 99–116, 2000

    2000

  30. [30]

    Gratton, A

    S. Gratton, A. Sartenaer, and Ph. L. Toint,Recursive trust-region methods for multiscale nonlinear optimization, SIAM J. Optim.19(1), 414–444, 2008

    2008

  31. [31]

    Brandt and D

    A. Brandt and D. Ron,Multigrid solvers and multilevel optimization strategies, inMultilevel NLF: A LINEAR-TIME SOLVER FOR NETWORK-FLOW EQUILIBRIA25 Optimization in VLSICAD, J. Cong and J. R. Shinnerl, eds., Kluwer Academic Publishers, Boston, 2003, pp. 1–69

    2003

  32. [32]

    Nocedal and S

    J. Nocedal and S. J. Wright,Numerical Optimization, 2nd ed., Springer, 2006

    2006

  33. [33]

    R. S. Dembo, S. C. Eisenstat, and T. Steihaug,Inexact Newton methods, SIAM J. Numer. Anal.19(2), 400–408, 1982

    1982

  34. [34]

    Brandt,Multi-level adaptive solutions to boundary-value problems, Math

    A. Brandt,Multi-level adaptive solutions to boundary-value problems, Math. Comp.31(138), 1977 (Full Approximation Scheme)

    1977

  35. [35]

    Brandt and O

    A. Brandt and O. E. Livne,Multigrid Techniques: 1984 Guide with Applications to Fluid Dynamics, Revised Edition, SIAM, 2011 (frozen-τ§15; discontinuities§4.6; global con- straints/continuation§5.6,§8.3)

    1984

  36. [36]

    Y. Gao, R. Kyng, and D. A. Spielman,AC(k): Robust solution of Laplacian equations by randomized approximate Cholesky factorization, SIAM J. Sci. Comput.48(3), A1643– A1684, 2026

    2026

  37. [37]

    Napov and Y

    A. Napov and Y. Notay,An efficient multigrid method for graph Laplacian systems II: robust aggregation, SIAM J. Sci. Comput.39(5), S379–S403, 2017

    2017

  38. [38]

    Bar-Gera,Origin-based algorithm for the traffic assignment problem, Transportation Sci

    H. Bar-Gera,Origin-based algorithm for the traffic assignment problem, Transportation Sci. 36(4), 398–417, 2002

    2002

  39. [39]

    Bar-Gera,Traffic assignment by paired alternative segments (TAPAS), Transportation Res

    H. Bar-Gera,Traffic assignment by paired alternative segments (TAPAS), Transportation Res. Part B44(8–9), 1022–1046, 2010

    2010

  40. [40]

    Peyr´ e and M

    G. Peyr´ e and M. Cuturi,Computational Optimal Transport, Foundations and Trends in Ma- chine Learning, 11(5–6):355–607, 2019

    2019

  41. [41]

    Essid and J

    M. Essid and J. Solomon,Quadratically regularized optimal transport on graphs, SIAM J. Sci. Comput.40(4), A1961–A1986, 2018

    2018

  42. [42]

    R. L. Tobin and T. L. Friesz,Sensitivity analysis for equilibrium network flow, Transportation Sci.22(4), 242–250, 1988

    1988

  43. [43]

    R. T. Rockafellar,Network Flows and Monotropic Optimization, Wiley, 1984 (reprinted Athena Scientific, 1998)

    1984

  44. [44]

    Boyd and L

    S. Boyd and L. Vandenberghe,Convex Optimization, Cambridge University Press, 2004. Free PDF athttps://web.stanford.edu/~boyd/cvxbook/

    2004