Skip to content

[ENH] Use column pivoting in the path follower's Givens QR, and remove the diagonal perturbation #1172

Open

Description

@tturocy

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions