You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
[ENH] Use column pivoting in the path follower's Givens QR, and remove the diagonal perturbation #1172
GivensQR::Decompose (src/solvers/path/path.cc) reduces the transposed Jacobian with the equations (columns) in fixed order. When an equation's gradient is nearly dependent on the earlier ones, the diagonal entry R(m,m) is tiny, and the triangular solve in NewtonStep divides by it. The homotopy work (ded034d) guards against this by perturbing the factor after decomposing: any |R(i,i)| < b_tol = 1e-10 is moved away from zero by b_pert = 1e-8 (path.cc, around line 330). Logit's equations (sum-to-one and ratio rows with ±1 entries on each player's own block) keep this away in practice; the homotopy system does not.
Proposed:
Pivoting: QR with column pivoting. At each stage, eliminate the remaining column with the largest residual norm. This permutes the equations only, so the tangent (the null vector of the Jacobian) is unchanged in direction.
Orientation: today, fixed-order Givens yields a consistently oriented tangent because every rotation leaves a positive diagonal. With pivoting, determine orientation from the determinant instead: with rotations, det Q = +1, so the sign of det[Jᵀ | t] is sign(P) · ∏ R(i,i). Choose t's sign to keep it constant along the path, preserving bifurcation detection (#1137).
Remove b_pert.
Keep rows contiguous: swap columns physically, so the row-rotation inner loop (#1166) is unaffected.
Before changing anything:
Add an HP case that currently depends on the perturbation to the golden tests, so the change can be shown to remove the need for it rather than just alter the path.
Confirm with the author of ded034d that pivoting addresses the cases the perturbation was introduced for.
Traced paths will change slightly, so affected golden files (tests/test_games/golden_logit) will need deliberate regeneration.
This is also a prerequisite for a Householder or LAPACK factorisation backend, which does not provide the tangent orientation as a by-product.
Activity