Static 1x1 LDLᵀ (sds_pivoting = :none) fails under ND ordering on a KKT matrix that AMD, :diag and :bk factor
Maintainers usually reply within 1 day
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 48/100
Research direction
Start with the fused static LDLᵀ factorization path and its nested-dissection ordering, then run sds_issue_repro.jl from the linked gist on the supplied matrix. Compare the failing :none/algo4 case with the successful AMD, :diag, and :bk cases while tracing the pivot reported at 18777. Done means the ND case factors successfully with the expected inertia, matching the other successful configurations.
Written by the indexing model from the issue text.
Description
Summary
On a saddle-point KKT matrix from an interior-point iteration, the fused static LDLᵀ with sds_pivoting = :none reports a failed factorization (info = 18777, no perturbed pivot) under the nested-dissection ordering, while the same matrix factors under AMD and under :diag and :bk pivoting, each with the expected inertia. ShiftedKKT.jl's signed Cholesky kernel, run on the same matrix in the same ND permutation, factors it with zero replaced pivots and a bare-solve relative residual of 3e-8, so the failing pivot is not numerically tiny.
Matrix
Lower triangle of the first MadNLP KKT matrix of COPSBenchmark.robot_model(1600) (ExaModels backend), n = 24022, nnz = 126446, rows 1:14410 primal, 14411:24022 dual. MatrixMarket file and the script below: https://gist.github.com/sshin23/6a0e0cd20651fe1119d11892906f6dc4
Column 18777 (the reported failure, a dual row) holds six entries all of magnitude at most 5.6e-9; primal diagonal entries reach 1e20 (MadNLP's fixed-variable parameters). A non-finite intermediate rather than a small pivot looks like the likelier mechanism, but that is a guess from the outside.
Reproducer
sds_issue_repro.jl in the gist builds SDSSolver through the MadNLP extension and calls MadNLP.factorize!:
base = (; n_primal = 14410, sds_factorization = :ldl, sds_stabilize = true, sds_pivot_signs = :block, sds_pivot_epsilon = 1e-10)
M = SDSSolver(CuSparseMatrixCSC(K); opt = SDSSolverOptions(; base..., sds_pivoting = :none, sds_reordering = "algo4"))
MadNLP.factorize!(M); M.last_info # 18777
Output on a Quadro GV100 (CUDA 12.9, Julia 1.13.1), fused-bk-factor at fb3b55e:
pivoting :none, reordering algo4 (ND) info = 18777 inertia = (24020, 1, 1) perturbed pivots = 0 (expected (14410, 0, 9612))
pivoting :none, reordering algo3 (AMD) info = 0 inertia = (14410, 0, 9612) perturbed pivots = 0
pivoting :none, no stabilization info = 18777 inertia = (24020, 1, 1) perturbed pivots = 0
pivoting :none, pivot_epsilon 1e-6 info = 18777 inertia = (24020, 1, 1) perturbed pivots = 9606
pivoting :diag info = 0 inertia = (14410, 0, 9612) perturbed pivots = 0
pivoting :bk info = 0 inertia = (14410, 0, 9612) perturbed pivots = 0
The same failure appears with sds_user_perm set to ShiftedKKT's permutation (info = 18799), with and without the Ruiz equilibration / dual shift of the shifted-KKT options, and on an NVIDIA H200. In an IPM run this surfaces as MadNLP regularizing the matrix to its limit at iteration 0 and failing restoration; the same happens on elec_model(800), marine_model(6400), robot_model(3200) and robot_model(6400).
- Dominant language
- Julia
- Stars
- 4
- Forks
- 0
- Avg merge
- 4h 1m
- Merged PRs (30d)
- 73
Getting set up
- No Dockerfile or Docker Compose file
- Has a pull request template
- No contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from exanauts/SparseDirectSolver.jl
-
found-by-agent
Difficulty 4/5 3-5 days Newbie friendliness 18/100
exanauts/SparseDirectSolver.jl#138 ·
Maintainers usually reply within 1 day
-
found-by-agent
Difficulty 4/5 3-5 days Newbie friendliness 18/100
exanauts/SparseDirectSolver.jl#137 ·
Maintainers usually reply within 1 day
-
T31 — oneAPI and Metal extensions, allocation-free KA dense fallbacks (issues #112, #53)Possibly taken @dmaldona claimed this 12 days ago. Opentask
Difficulty 5/5 Over a week Newbie friendliness 12/100
exanauts/SparseDirectSolver.jl#118 ·
Maintainers usually reply within 1 day
-
task
Difficulty 4/5 3-5 days Newbie friendliness 20/100
exanauts/SparseDirectSolver.jl#117 ·
Maintainers usually reply within 1 day
-
task
Difficulty 5/5 Over a week Newbie friendliness 8/100
exanauts/SparseDirectSolver.jl#116 ·
Maintainers usually reply within 1 day
All issues in exanauts/SparseDirectSolver.jl
Similar issues
-
io
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
Maintainers usually reply within 1 day
-
Difficulty 1/5 Under an hour Newbie friendliness 72/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
JuliaGPU/GPUArrays.jl#837 ·
Maintainers usually reply within 2 days
-
Difficulty 1/5 Under an hour Newbie friendliness 88/100
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
bmad-sim/BeamTracking.jl#382 ·
Maintainers usually reply within 1 day