Written by Claude Fable 5.1 — both this text and the code it describes; posted by @BoykoNeov.

@jwesthues @phkahler @ruevs — the "human understanding" of the #1748 regression, and a revision of #1748 that removes it. Measured on master 952c11c0, Release and Debug, nothing here is a claim about code you cannot fetch: fix-1247-newton-damping-v2 (one commit, e298c5e2, off 952c11c0).

Why #1748 fails on #1105's sketch

problem.slvs, constraint c4 is an angle between two lines, authored at 35°. Set it to 5° and re-solve. Master converges in 11 iterations; #1748 spends its 50 and gives up with the angle still at 35°. Traced per iteration, with the equations carrying the residual:

master  start:      |F|^2 = 0.215   [c4 ANGLE 0.464]
        full step:  |F|^2 = 1960    [c31 PT_PT_DISTANCE 39.3] [c35 PT_PT_DISTANCE 20.3] [c17 PT_ON_LINE 0.93] [c4 ANGLE 0.116]
        then:       167  3.4  0.015  7e-7  2e-15  3e-26   OKAY
#1748   full step rejected (1960 > 0.215); 1/2 -> 126, 1/4 -> 8.1, 1/8 -> 0.66, 1/16 -> 0.221, 1/32 -> 0.204 accepted
        then 1/32 or 1/16 of a step for the remaining 45 iterations; |F|^2 0.183, 0.165, 0.153, 0.142, 0.131 ... budget spent

The full Newton step fixes the angle to first order and, because the equations are nonlinear, leaves two point-to-point distances off by 39 mm and 20 mm. Master takes it and Newton removes those quadratically. The line search refuses it, because its merit is |F|^2, and |F|^2 adds the square of a cosine difference to the squares of two lengths in mm: on that yardstick 0.2 → 1960 is "ten thousand times worse". So it halves the step until the distances stay small, accepts 1/32 of a step for a 5% gain, and from there the Newton direction hardly changes (step norm 466 → 317 over 50 iterations, always the same way), so it crawls at 1–3% per iteration. The merit mixes units; it cannot compare an angle error with a distance error; so it refuses the one step that solves the sketch. That is also what your "linearized about a different point" objection looks like in practice.

Two of your three suggestions were measured on the way, and on this model both go the wrong way for that merit: at 60°, #1748 crawls at 1/128 for 14 iterations until nothing improves, then its full-step fallback fires (0.095 → 7776) and it converges three iterations later; the fallback is what rescues it. Taking the smallest step instead, or failing, turns 60° into a second regression. And "fail entirely" as literally written fails every already-solved group, because on a zero residual no step is strictly better, so the search burns all eight tries every call — that is also where #1748's 4.5× residual evaluations came from (768 of 7663 in a drag on this file are exactly that).

The revision

Three changes to #1748, in src/system.cpp only:

Measure distance, not |F|^2. Each equation is weighted by the inverse norm of its Jacobian row: F_i/|∇F_i| is the first-order distance to the set where equation i holds, in parameter units, whatever the units of F_i. The row norms are one pass over a Jacobian that is computed anyway. Under this merit master's full step on c4 → 5° is a 68 000 → 6 000 improvement, so it is accepted, and the trajectory is master's step for step.
Convergence is tested before the search, not only after the step. That fixes the point above, and it also skips the Jacobian factorisation master does unconditionally on every already-solved sub-system: in a drag that is half (the Cannot extend reference line in simple sketch #1105 file) to five sixths (the Circle inexplicably cannot resize more than 16384 #246 file) of all factorisations.
If not even 1/128 of the step improves the merit, fail, as you suggested. Under this merit the three fallbacks — smallest step, full step, fail — give identical results on every case of both corpora, because it only fires in solves that fail anyway; so your preference costs nothing and is the cheapest.

IsReasonable() stays. You are right that a NaN is rejected by NaN < err being false, and the comment now says so; but it also rejects anything past ±1e11, and that does something — removing it changes exactly one case in 808 (arcs.slvs, a dimension taken to 1000× its value, where the full step throws a parameter past 1e11 and the solve then recovers 28 iterations later). Not worth a convergence test that a NaN passes. "Max damping coefficient < 1" was measured too (0.9 and 0.5): never taking the full step makes the iteration linear, 82 of 648 fixture cases land somewhere else and at 0.5 six of them run out of budget. Dropped.

Breadth

Same corpora and buckets as the step-4 study: 648 fixture cases (30 distinct sketches, 81 dimensions × 8 targets) and 160 cases on 11 reporter models from #1105, #1378, #1466, #1723. R = master solves and the arm does not; W the reverse; X both solve but land somewhere else (> 1e-6 relative).

arm	fixtures R / W / X	models R / W / X	Jacobian factorisations, fixtures	residual evaluations
master	—	—	1565	1565
#1748 as reviewed	0 / 6 / 6	1 / 2 / 7	1565	7663
#1748, smallest-step fallback	0 / 6 / 6	2 / 2 / 6
#1748, cap 0.9	0 / 6 / 82	2 / 2 / 43
revision	0 / 6 / 6	0 / 2 / 11	811	824

Identical in Debug. The two wins are #1748's, kept. On X: #1748's seven include two landings that differ from master's by 40% and 180% of a parameter, i.e. a different solution; the revision's eleven are all between 1e-6 and 8e-5 relative (the largest is 4 µm on an 8 mm coordinate) and come from the entry check — master always takes one Newton step even on a solved system, and on that file's near-redundant parallel constraints it polishes a 1e-11 residual into a 3 µm move.

The 6480-pair flip grid on #1748's own fixture is unchanged from #1748 to the revision, to the pair: 6480 solved, 547 flips on the 5662 pairs master solves (88 of master's 619 removed, 16 added). That fixture has one kind of equation, so the merit cannot change anything there.

Drag regime, headless harness, Release, whole-drag wall time: master, #1748 and the revision are within noise of each other (~55 ms for 193 moves on #1105's file; the solver is a small part of a frame). The counts are what differ: 1519 / 1519 / 751 factorisations for master / #1748 / revision on that drag, 1920 / 1920 / 336 on the #246 file. Every frame OKAY in all three.

Suite: 266 cases / 949 checks, all passing, Debug; master's 265 / 944 plus exactly #1748's test.

What is not claimed

No "strict superset" of master; it is 0 regressions on 808 cases plus the grid, measured. The merit is first-order: at a critical point of one equation its row is zero and that residual counts raw. Not tested on macOS/Linux compilers, nor with OpenMP off.

Full write-up with every arm, the raw traces and the scripts: available on request.

Uh oh!

Release version 3.3 #1764

Description

Activity

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions