Ordering chooser picks AMD on large KKT systems: cost model weighs column-etree depth, not supernodal schedule depth (2× schedule depth vs ND) #108

Found while working on: PR #107 (performance prototypes, experiments 0/5/6; ordering study bench/order_search.jl, bench/solve_nd.jl)

What: the automatic ordering choice (compute_ordering, src/symbolic/ordering.jl, reordering_alg = "default") picks AMD on large KKT systems where ND is 2× better for the GPU. ordering_cost(flops, nlevels, n) = flops × (1 + nlevels/n) weighs depth at ~0.2% for n = 674 562 (the 78k-bus pglib condensed KKT), so the chooser is a flop contest that AMD wins; and nlevels is the column-etree depth, which does not predict the supernodal schedule depth that governs GPU time (cuDSS's permutation: 1279 column levels → 30 schedule levels; METIS: 1216 → 29; AMD: competitive column metrics → 65 schedule levels). Forcing reordering_alg = "algo4" on that matrix: schedule depth 65 → 29, solve 36% faster, factorization 11–17% faster (GV100). A METIS knob sweep (seed, ufactor, nseps) moves schedule depth 28–41 with noise; plain ND is enough.

Why it is out of scope: #107 is a bench-level campaign; the cost model is T05 code and a PLAN §2.3 step 2 decision. Does not block a task; it makes every GPU run on large KKT systems slower by default.

Suggested fix or plan change: score candidate orderings by supernodal schedule depth (cheap: compute the supernode partition and tree_levels(snparent) per candidate, as the T06 Report already suggested), with a weight that matters at n ≈ 1e6; or prefer ND on GPU backends and keep AMD for the CPU backend. Owner note under T25; PLAN §2.3 step 2 updated in the docs PR that cites this issue.

Generated by Claude Code