In-front Bunch–Kaufman pivoting for the fused pipeline: state of the closed prototypes #135 and #139

Open
  • Is something wrong?
#167 0 comments 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
5/5
Estimated time
Over a week
Newbie friendliness
20/100
Issue type
Feature
Clarity
Clearly specified
Activity status
Active
Tech stack
julia
Domain
backend, databases

Research direction

Read src/fused.jl, the closed PRs #135 and #139, and the testset fused solve on a pivoted factor in test/test_solve.jl to understand the failed prototype and current FusedSolver pipeline. The issue proposes reconsidering this work only after T34 and T24–T26, as a staged task starting with a pivot-aware fused solve and passing CUDA and AMDGPU tests. Done means the solve test passes on both platforms before factorization work begins, with :bk_hybrid as the target and no wide-front in-front BK.

Written by the indexing model from the issue text.

Description

design-record enhancement found-by-agent fused madnlp

Found while working on: housekeeping after T33 (PRs #135 and #139, closed unmerged on 2026-10-29)

What: In-front Bunch–Kaufman pivoting for the fused pipeline (src/fused.jl) was prototyped on branches fused-bk (#135, the pivot-aware fused solve) and fused-bk-factor (#139, the pivoted fused factorization, :bk_hybrid, :diag, lazy stabilization, MadNLP extension options). Both PRs were closed without merging:

  • The shared first commit (5947a93, the pivot-aware fused solve) fails its own testset fused solve on a pivoted factor in test/test_solve.jl on CUDA, ROCm and the RTX 4080 with the bit-identical wrong answer (relative error 16.06 against a tolerance of 9e-6 in Float64, 23.2 against 0.21 in Float32), i.e. a deterministic logic bug in the pivot-aware fused solve, not a race. The PR's claim of a clean GV100 suite did not reproduce anywhere.
  • #139 was 11 commits on top of that, the last two marked WIP and never regression-gated, and conflicted with main in src/fused.jl, src/numeric/ldlt.jl and ext/SparseDirectSolverMadNLPExt.jl after T33 turned the fused module into FusedSolver (~500 lines of src/fused.jl changed on main since the branch point). A rebase would be a reimplementation.

The branches remain on origin for reference. Findings worth keeping from #139's description and commits, so they are not re-derived:

finding detail
cost of in-front BK at fused speed (78k condensed ACOPF KKT, GV100) no-pivot fused LDLᵀ 0.0475 s; :bk_hybrid (BK subtrees + narrow fronts, unpivoted wides) 0.0874 s (1.84×); full :bk with vendor-sytrf wides 0.257 s; stock BK 0.450 s; cuDSS 0.030 s
end-to-end (INFORMS 66-case ACOPF, L40S) condensed + SDS goes 60 → 64 solved with :bk_hybrid, equal to condensed + cuDSS with the same two failures (9241_pegase, 1888_rte); wide-front pivoting was not load-bearing (5× repeat of :bk vs :bk_hybrid identical)
wide-front in-front BK does not honor its own threshold pivoting restricted to the fully-summed block accepts sub-threshold pivots when no candidate passes against the full column; on the 78k the stock BK wide-front multipliers reach 4.6e4, larger than the unpivoted path's 3.9e4, 53 of 58 wide fronts over the bound. An optimistic fast path certified by `
cuSOLVER sytrf factor form same ipiv as LAPACK but the product form ∏ₖ(PₖLₖ): earlier L columns are not row-swapped. LAPACK-style reconstruction fails at 0.97 relative error, the product form reconstructs to 3e-16
KA barrier rule @synchronize inside one arm of an if/else deadlocks (threads in the other arm never arrive); the work may be conditional, the barrier may not. Surfaced as a hung test_numeric_ldlt on CUDA
tuning that did not pay widening the subtree pivot search (neutral), 512-thread BK panels (no better than 256), subtree workgroups of 64 or 32 (worse than 128). Remaining +0.040 s: mega-kernel BK panels +0.027 s, pivoted subtree launches +0.017 s, the per-pivot-step serial chain (search → decide → update)
BK 2×2 determinant bound a BK-chosen pair has det < 0 strictly with |det| ≥ (1 − α²)λ², so the (1 pos, 1 neg) inertia credit is never wrong for it; what is reachable is a tiny diagonal with a partner far above λ, giving an inverse entry above 1/eps (commit 59e85bf on fused-bk-factor, reference mirror + derived fixture, test_reference_ldlt 975/975 on CPU)
lazy stabilization (sds_stabilize, WIP) perturbing zero diagonals to ±1e-13 completes the factorization with info = 0 and an inertia for MadNLP to regularize against, but the standalone solve stays poor (relative error 2–3); any such cell must be labelled that way (commit fb3b55e)

Why it is out of scope: none in TASKS.md. PLAN.md defines the fused pipeline as Cholesky and no-pivot LDLᵀ; T34 (#156) is performance work on that pipeline, and T24–T26 are the stock pivoted kernels under DirectSolver. The MadNLP extension's sds_pivoting = :bk routes through the stock in-front BK path (#134) in the meantime. Does not block a later task.

Suggested fix or plan change: if pivoting at fused speed is wanted after T34 and T24–T26, cut it as a task on the FusedSolver of T33 with the stage order of #139 (pivot-aware fused solve first, with its testset passing on CUDA and AMDGPU before the factorization stage), :bk_hybrid as the target configuration, and no wide-front in-front BK.

Dominant language
Julia
Stars
7
Forks
0
Avg merge
7h 54m
Merged PRs (30d)
84

Getting set up

  • No Dockerfile or Docker Compose file
  • Has a pull request template
  • No contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from exanauts/SparseDirectSolver.jl

All issues in exanauts/SparseDirectSolver.jl

Similar issues

More Julia issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.