Runtime analysis: the one-path verdict vs the retired span/tracking modes (measured)

What is on this page. The rebuild once carried two alternative a-posteriori verdict modes — “span” and “tracking” — that turned out to be artifacts of the reimplementation: source-reading the reference MATLAB implementation shows a single algorithm, and the fork was collapsed onto that one faithful path on faithfulness grounds. This page quantifies the runtime side of that decision: a per-edge cost model of the surviving pipeline (theory + measured), an end-to-end A/B against both retired modes on the §3.3.2 / §3.3.3 problems, a cost-vs-fidelity verdict, and a ranked list of optimization opportunities quantified against the measured profile.

Measurement design. An instrumented A/B harness in the project repository runs unmodified on the current tree and on the last revision that still carried both retired modes, timing each verdict-pipeline phase in place. Every eigensolve uses a fixed ARPACK start vector, so solve counts, grids, and verdicts are deterministic and exactly comparable across the two revisions; wall-clock figures are medians of 3 repeats.

1. The per-edge cost model (theory)

Per tested edge, the one-path verdict executes, on snapshots of k eigenvectors over n_dof FE degrees of freedom with a sparse mass matrix M̄ (nnz ≈ c·n_dof):

Phase Work Complexity Notes
midpoint assembly assemble K, M at the edge midpoint O(n_dof) (affine cache) the assembled K is discarded — only M̄ is used
projection (optional, default on) cluster detection + per-cluster M̄-projection O(k²) + O(n_dof·Σ|c|²) cluster-gated; near-zero when no t_λ-clusters exist
cost matrix |λᵢ−λⱼ| gaps + Vₐᵀ(M̄ V_b) overlap + per-cluster SVDs O(n_dof·k²) one SpMV + one dense matmul
Hungarian assignment linear assignment on the (k, k) cost matrix O(k³) negligible at k ≤ 25
overlap matrix Π Π = |Vₐᵀ(M̄ V_b)| on the reordered snapshots O(n_dof·k²) a second SpMV + dense matmul — an exact permutation of the cost-matrix overlap (see §5)
verdict inline anchored prune + survivor-count verdict + t_c surplus gate O(k²) negligible in flops

The two O(n_dof·k²) overlap products dominate the pipeline. Against the retired modes:

  • old “tracking” (first-k): no Hungarian, no cost matrix — identity pairing on raw ARPACK order; an optional cluster rewrite before Π; and, in one variant, a post-verdict cross-side cluster-exemption pass. One overlap product instead of two.
  • old “span”: Hungarian always (like the one path), no projection, and a verdict that ran per-pair cluster-neighbour scans (O(pairs·k)).
  • old “tracking” (window): Hungarian + the tracking verdict — structurally the closest ancestor of the one path.

So per edge the one path does strictly more work than old first-k tracking (adds cost matrix + Hungarian) and about the same as old span (adds optional projection). None of this matters unless the pipeline is a material share of wall-clock — which is what §2 measures — because every bisected edge costs one eigensolve: a sparse LU of (K − σM) plus Krylov iterations, O(n_dof^α) with α well above 1, typically 100–1000× the per-edge pipeline cost.

The structural consequence: total runtime across modes is driven by verdict behavior — how many edges each mode flags, hence how many eigensolves and levels a run performs — not by per-edge pipeline cost. A mode that certifies earlier is cheaper end-to-end even if its per-edge pipeline is heavier.

2. Per-edge phase profile (measured)

Measured per-edge phase means over whole runs (median wall of 3 repeats; mesh resolution 64 → n_dof≈3969 for §3.3.2, mesh resolution 32 → n_dof≈961 for §3.3.3):

Phase (µs/edge) §3.3.2 first-k k=6, n_dof≈3969 §3.3.3 first-k k=5, n_dof≈961 §3.3.3 window (ragged k≈15–20)
midpoint assembly 369 172 299
verdict 135 99 1004
cost matrix 132 58 151
overlap matrix Π 92 30 106
projection 58 33 328
Hungarian assignment 53 32 66
edge test total 898 451 2040

Three facts the theory table alone would not predict:

  1. Midpoint assembly is the largest phase (33–41% of the pipeline), not the overlap products — and it assembles a stiffness matrix it then throws away, for a mass matrix that is parameter-independent on both diffusion problems.
  2. The verdict is Python-loop-bound, not flop-bound. Its O(k²) is asymptotically negligible, but the per-band inline-prune loop runs as interpreted Python; under ragged window snapshots (k≈15–20) it becomes the single largest phase at ~1 ms/edge — half the pipeline.
  3. The duplicated overlap product (the cost matrix and Π both compute VₐᵀM̄V_b) costs ~90–100 µs/edge — real, but ~10% of the pipeline, not half.

Pipeline share of total wall-clock: 3–17% across the matrix (3–5% on the n_dof≈3969 1-D cells, 10–17% on the n_dof≈961 2-D cells — the share falls as n_dof grows because the eigensolve scales super-linearly while the pipeline is linear in n_dof). Eigensolves take 24–83% of wall (the run-length-dependent remainder is store/graph bookkeeping and, on the shortest runs, fixed setup). At the §4.4 scale (n_dof≈6000) the pipeline share is smaller still. Per-edge cost is second-order; the mode comparison in §3 is decided by solve counts.

3. End-to-end A/B: one path vs span vs tracking (measured)

Controlled cells — same problem, mode, band count, thresholds (the reference-faithful additive pruning rule throughout); only the verdict machinery varies. Solve counts, grids, and verdicts are deterministic under the fixed solver start vector; wall is the median of 3. Fidelity is ROM-vs-dense relative eigenvalue error (L₂ over held-out interior queries), first-k cells only.

§3.3.3 2-D first-k (k=5, t_π=0.57, t_λ=0.015, level cap 8)

Variant Solves Terminates Nodes Wall (s) ROM L₂
one path (current) 17 L=3 17 0.13 2.5e-6
span (retired) 19 L=3 19 0.15 3.0e-5
tracking + rewrite (retired) 19 L=3 19 0.16 3.0e-5
tracking + cluster exemption (retired) 21 L=3 21 0.18 1.5e-5
tracking (retired) 33 hit the L=8 cap 33 0.26 4.9e-5

The one path strictly dominates on 2-D first-k: fewest eigensolves and 6–19× better ROM fidelity than every retired variant. Plain old tracking (identity pairing, no gauge alignment) never converges — raw ARPACK band order across a 2-D box mismatches often enough to keep flagging until the level cap.

§3.3.2 1-D first-k (k=6, t_π=0.21, t_λ=0.001, level cap 8)

Variant Solves Terminates Nodes ROM L₂
one path (current, projection on or off) 4 L=1 4 1.9e-3
span (retired) 21 L=8 21 3.2e-5
tracking (retired) 22 hit the L=8 cap 22 3.2e-5
tracking + rewrite (retired) 21 L=8 21 3.2e-5

The honest non-dominant cell: the faithful survivor-count verdict certifies this 1-D spectrum at L=1 (4 nodes), where the old span verdict’s extras-inside-cluster rule kept flagging to L=8 — 5× fewer solves for ~60× coarser fidelity. Two qualifiers keep this from being a regression verdict: (a) this first-k configuration is an acknowledged approximation of §3.3.2 — the reference ran the example in window mode (next table), where the old and new trees agree exactly; (b) the extra fidelity the old modes bought here was an accident of an unfaithful refine rule, equivalent to running the one path at tighter tolerances. If §3.3.2 first-k fidelity matters, tighten t_π/t_λ (the documented lever — see the tolerance-perturbation study) rather than mourn the fork.

Window mode (the faithful mode)

Group Variant Solves Terminates Nodes
§3.3.2 I_λ=[0,270] one path (current) 8 L=3 8
tracking (retired) 8 L=3 8
§3.3.3 I_λ=[0,200], capped at 4 levels one path (current) 50 hit the L=4 cap 50
tracking (retired) 45 L=4 (converged) 45

On the faithful 1-D reproduction the two trees produce identical grids and identical solve counts — the consolidation was cost-neutral where it claimed to be behavior-preserving. On the capped 2-D window run the one path flags ~11% more edges (50 vs 45 solves) and is still refining at the cap; the delta comes from the consolidated verdict (the inline anchored prune and the surplus-band gate on one code path), and it buys a correctness fix the old window-tracking path lacked: the matching stored on each edge is now the raw Hungarian pairing, so the ROM evaluator indexes stored eigenvectors correctly.

4. Decision

The one path is the right algorithm, on runtime grounds as well as faithfulness. Summing the evidence:

  • Per-edge cost differences between the three machineries are noise in context: the pipeline is 3–17% of wall at benchmark scale and shrinking with n_dof; the feared “the one path always runs Hungarian now” overhead is ~30–66 µs/edge.
  • Where total cost diverges, it diverges through verdict behavior, and there the one path wins outright (2-D first-k: strictly dominant), ties exactly (1-D window: identical grid), or trades honestly (1-D first-k: certifies earlier — cheaper and coarser, tunable via tolerances; 2-D window: ~11% more solves buying a correctness fix).
  • The retired modes carry disqualifiers runtime can’t offset: plain tracking fails to converge on 2-D first-k (level-cap blowout, 2× the solves of the one path), and the old window-tracking path mis-indexed the ROM.

No measured result argues for resurrecting either retired mode.

5. Improvement opportunities (proposed, ranked)

Ranked by measured share × fraction removable. None are implemented here.

  1. Cache the midpoint mass matrix (and stop assembling the discarded stiffness matrix). Midpoint assembly is the largest pipeline phase (33–41%, §2) and, for both diffusion problems, the mass matrix does not depend on µ at all — one assembly per problem would do. Removes ~⅓ of the pipeline ≈ up to ~6% of wall at 2-D benchmark scale.
  2. Vectorize the verdict’s inline prune loop. Dominant under window mode (~1 ms/edge, half the ragged-Π pipeline). The MATLAB-faithful same-loop mask mutation constrains the order of operations but not the inner representation — the per-band row/column survivor scans can be NumPy-masked instead of Python-looped. Matters exactly where the faithful reproductions run (window mode).
  3. Reuse the cost-matrix overlap for Π. The Π step recomputes the VₐᵀM̄V_b product the cost matrix already computed; since the reorder is a pure column permutation and projection precedes both, Π is exactly a permuted absolute copy of that overlap. Removes ~10% of the pipeline (~90–100 µs/edge).
  4. Parallelize the sequential edge-test loop the way the bisection phase already uses the bounded worker pool (see parallel execution). Bounded by the pipeline share (≤17% at benchmark scale, less at the §4.4 scale) — only worth it bundled with a window-heavy workload, after (2).
  5. Factorization caching for (K−σM). The only lever on the dominant cost — eigensolves are 67–83% of wall on the longer runs. Out of scope for the verdict pipeline but first in line for any real wall-clock program. (A companion catalogue of open scalability problems, not yet published, tracks this seed.)

6. Provenance

The measurements were produced by an instrumented A/B harness in the project repository; the raw per-phase and per-run records are committed alongside it, guarded by a schema test that deliberately pins no machine-specific wall-clock numbers.