ADR-018: godunov — Lebacque (1996) Godunov scheme + the first non-triangular FD

Status: accepted (implemented) Date: 2026-07-09 Deciders: DNL-models track — the general-FD Godunov scheme (first rarefaction physics) File: docs/design/adr-018-godunov.md

Context

ctm (adr-015) is the Godunov scheme for the triangular fundamental diagram. Lebacque (1996) frames the Godunov scheme for any first-order (LWR) model via the demand/supply (Delta/Sigma) flux — exactly the fd.demand_at/supply_at interface the dnl-core already exposes. The genuinely new content this sprint adds over ctm is a smooth, non-triangular concave FD and the rarefaction fan physics it produces — a triangular FD produces only shocks and contact discontinuities, so no benchmark test has ever exercised a rarefaction.

Decision

  1. GreenshieldsFD in fd.py — the first smooth, strictly concave FD, Q(k) = vf·k·(1 - k/kappa) (k_c = kappa/2, q_max = vf·kappa/4, vf = Q'(0), w = |Q'(kappa)| = vf). Its Lebacque demand Q(min(k, k_c)) and supply Q(max(k, k_c)) give the exact Godunov flux min(demand, supply) for a concave FD, and its inherited envelope_params triangular majorant (vf, vf, kappa) is sound: Q(k) <= min(vf·k, vf·(kappa - k)) with equality only at the endpoints.

  2. GodunovLink(CTMLink) in godunov.py — reuses the verified CTMLink cell update unchanged (the scheme is identical; only the FD differs), substituting a GreenshieldsFD built from the link’s (vf = free_speed, kappa = jam_density). The transonic Godunov flux is entropy-correct by construction: at an interface k_L > k_c > k_R (a rarefaction spanning the sonic point) min(demand(k_L), supply(k_R)) = q_max, the maximum-flux sonic value.

  3. Certifier unchanged — the triangular majorant is sound for the concave FD. The certifier reads dynamics.fd(a).envelope_params() and dynamics.capacity (a triangular majorant + capacity), NOT GodunovLink’s FD; because Greenshields is majorized by (vf, vf, kappa) and its capacity is vf·kappa/4, a Greenshields loading certifies with no certificate change (its parabolic free-flow speed vf(1 - k/kappa) < vf is slower than the Newell vf envelope, so C4 holds a fortiori). GodunovLink guards that the LinkDynamics is Greenshields- consistent (wave_speed == free_speed, capacity == vf·kappa/4) so the certifier never gates against a mismatched capacity.

Analytic anchors (machine-verified — test_dnl_godunov.py)

  • GreenshieldsFD: derived quantities, the parabolic flow/demand/supply branch values, majorant soundness, validation.

  • Transonic Godunov flux: min(demand(3.5), supply(0.5)) = q_max = 2 (the entropy-correct rarefaction value, not a shock value).

  • Loader + certification: a Greenshields loading through NetworkLoader + DNLEvaluator certifies (dnl_feasible = 1), demonstrating the triangular majorant is sound for the smooth FD.

  • Rarefaction convergence (the distinguishing anchor): a dam-break Riemann problem (jam left, empty right) stepped by the Godunov flux converges to the analytic self-similar fan k(x,t) = (kappa/2)(1 - (x-x0)/(vf·t)); the L1 error shrinks monotonically as the cells are refined (0.128 → 0.041 over 20 → 160 cells — first-order Godunov, slowed by the sonic-point sqrt singularity).

Alternatives considered

  • A distinct GodunovLink cell update: rejected — the cell update is identical to CTM’s; only the FD differs. GodunovLink subclasses CTMLink, reusing the reviewed (and w>vf-hardened) code, and ships the new FD + rarefaction validation.

  • Extending LinkDynamics with an fd_kind field: deferred — GodunovLink building the Greenshields FD from (vf, kappa) (with a consistency guard) needs no change to the frozen LinkDynamics/scenario hash; a general FD registry can come when a second non-triangular FD ships.

  • An asymmetric (w < vf) smooth FD: deferred — Greenshields (w = vf) already exercises rarefactions; an asymmetric smooth FD is a follow-up if a w < vf rarefaction anchor is wanted.

Consequences

The benchmark gains its first non-triangular fundamental diagram and its first rarefaction physics, on the shipped cell scheme + certifier with no certificate change. All changes are additive (a new FD + a new link + tests + exports), so the 582-test suite, every road/DNL hash, and the golden Braess content hash are byte-untouched.

Sourcing

Lebacque (1996, ISTTT 13) “The Godunov scheme and what it means for first order traffic flow models” — the demand/supply Godunov formalism; open restatements circulate, attributed. Greenshields (1935) for the parabolic FD; Godunov (1959) / LeVeque Finite Volume Methods for Hyperbolic Problems for the exact-Riemann-solver flux and rarefaction theory. No DOIs or page-precise quotes reproduced.