Improved newton (BoykoNeov#4) - #1759
Conversation
Sorry, something went wrong.
Sorry, something went wrong.
|
I measured the five issues in the Closes list against this PR, since three of them had never been checked. Three are genuinely fixed, two are not shown to be — and one of the three reverses what I'd previously assumed. MethodTwo trees differing in nothing but src/system.cpp plus the new test:
src/system.cpp in the fix tree verified byte-identical to this PR's head. Both trees were given the same debugtool.cpp, so the tooling can't bias the comparison, and both builds were confirmed to exit 0 before any result was believed. Debug, Ninja/MSVC, OpenMP on, GUI off. The stepping path is what matters here: several of these only fail when a dimension is edited and the sketch re-solved from the previous solution, which is what the GUI does. Loading a file can't reproduce them. Results
Test suite: base 264 cases / 937 checks → fix 265 / 944, all green. The delta is exactly the seven checks in test/constraint/large_dimensions/test.cpp. No regressions. #1105 — this one reverses my own earlier read, and it has a trap in itI had assumed #1105 was a stepping problem in the #1247 family rather than a conditioning one, and so would not be fixed here. That was based on your own 2021 comment about needing ever-smaller steps and getting stuck around 3629. Measured, it is fixed by this PR. The trap, which is why it looks unfixed if you check it the obvious way: a direct 1000 → 4000 jump succeeds even on master. Only the gradual path fails. If you re-check this, step it. #1466 — checked twice, because it was the thinnest evidenceIt's a linked assembly, so a bare OKAY could be a converged-but-wrong solution. Two things settle it:
#246 and #267 — what I can and can't sayNeither reproduces on master, so closing them hides no live bug. But "doesn't reproduce" is not "fixed by this PR", and for #246 it isn't even the whole test:
Both are from 2017. I'd rather say what was tested than round it up. One mechanical note on the Closes listThe keywords are in your comment, not in the PR description, and GitHub only creates the closing link from the description or a commit message. As the PR stands, closingIssuesReferences returns exactly one issue — #1354 — and that comes from the Fixes #1354 trailer in 21a74715, not from the comment. So merging as-is would close #1354 only, and leave the other four open. Worth knowing either way, since it's easy to fix by moving the lines into the description if that's what you want. If you do move them: #1105, #1354 and #1466 are earned and now measured. For #246 and #267 I'd close them as not-reproducible rather than as fixed here, or leave them. Nothing above argues against merging. Written by Claude Opus 5 — both this text and the code it describes; posted by @BoykoNeov. |
Sorry, something went wrong.
|
I tested all models with the "solver" label and reported my results here BoykoNeov#4 (comment) but did not compare with master - so some of them may have indeed already be fixed. #1345 is one such. Issues linked in "development". Edit: #1354 indeed |
Sorry, something went wrong.
|
I was just rebasing those commits here so it'd be easy to apply. My list of fixes was based on @ruevs comment here with an assumption on my part that he meant to type 1354 instead of 1345. I have no idea how to link issues that will be closed by the PR - the dropdown/search on the right side of github doesn't work. Adding the comments here apparently doesn't work either even though I've seen that work in the past. We seemed to be in agreement that this is a good fix. For merging, my only blocking question is if we want the other one first. Claude rejected the later fix (was it number 7?) in a discussion I can't find. @ruevs had indicated 3 and 7 both fixed issue #1247 but seemed to not like 3, which the larger discussion had jwesthues and Claude both prefering 3 to 7. I agree about not taking 7 after reading the discussion. So we're going to take this change. Do we want BoykoNeov 3 ( #1748 ) first or not? |
Sorry, something went wrong.
This is orthogonal to #7 / #1749 and/or #3 / #1748. @jwesthues has valid objections to both of those. But we can merge this. I'll merge it. |
Sorry, something went wrong.
SolveLeastSquares() computed the minimum norm Newton step as x = A'*(A*A')^-1*B, forming A*A' explicitly and factoring it with a rank-revealing sparse QR. That squares the condition number of the Jacobian. Our equations mix dimensionless quantities with lengths and with areas, so the spread of magnitudes in A already grows with the physical size of the sketch; squaring it pushes the smallest pivot of A*A' below the threshold Eigen uses to call a column linearly dependent, which is proportional to the largest column norm. Eigen's rank-truncated solve then silently zeroes that component of the step, so the residual of one equation can never be driven to zero, Newton's method stalls, and a perfectly solvable sketch is reported as having incompatible constraints. On the file from the bug report, two 4 m lines constrained perpendicular with a point on line, the transition is exact: with the second line pinned at 4 m and the first at 2880 mm, the fifth pivot of A*A' is 3.657e-7 against a threshold of 3.6557e-7 and the sketch solves; at 2881 mm the pivot falls just below the threshold, the rank drops from 5 to 4, and the solve fails, with the step norm collapsing to 1e-13 while one residual stays pinned at 0.019. Factor A' = Q*R directly instead. Then A*A' = P*R'*R*P', so the same z = (A*A')^-1*B comes from two triangular solves against R, and the rank decision is taken on pivots that scale like A rather than like A*A'. In that same sweep, the longest first line that solves goes from 2.88 m to 76.9 km. Rank determination for redundant constraints is untouched; it runs in TestRank(), against A itself. Over-constrained sketches are in fact reported better than before: duplicating a constraint in that file used to be reported as redundant below about 3 m but as unsolvable above it, and is now reported as redundant at every size, out to 100 m. The wide case, more equations than unknowns, keeps using the normal equations, since Eigen's sparse QR wants a matrix that is at least as tall as it is wide. Such a system is redundant anyway, and it gives the same result as before. A system with no equations or no unknowns now returns a zero step, rather than multiplying an uninitialized vector by a matrix of a mismatched size. Also teach the debug tool to load a file and report how each group solved, and to load a file and save it back, which is how a linked part gets re-solved without a GUI. Fixes solvespace#1354, both the original report and mesr's assembly. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
The fixture is the file from the bug report, unmodified: two 4 m lines constrained perpendicular, with the start of the second one on the first. It has to be the file as saved, not a canonical re-save, because the failure depends on the stored parameter values being the ones from before the perpendicular constraint was added; re-saving it stores the solution, and then there is no Newton step left to take. The test checks the geometry as well as the solve result, since the constraints could be satisfied by more than one configuration. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
This is BoykoNeov #4 applied to solvespace master. This is the one we seem to agree is good. FYI I could not automatically rebase #1748 on this so it's not clear which shoud go first - assuming we even want that one.