Repository navigation
Solve is bounded on its Groebner path and unbounded on the fall-through, so the same call may or may not finish #896
Description
EquationSystem.Solve still runs for an unbounded time on a coupled polynomial system that the Gröbner path declines, because the fall-through has no budget of its own.
Split out of #860, which is otherwise done:
the Gröbner backbone is in and bounds itself. This is the one thing left, and it is a decision rather
than an obvious defect.
The measurement
master (f2594259), .NET 10, cyclic-6:
the whole Solve, 6 equations and 6 variables |
exceeds 20 s |
| the same system over-determined, so the fall-through throws immediately instead of running | 5 378 ms |
The second number is the Gröbner path alone, against its own 5 000 ms budget — 7.6% over, so it is
well behaved. The remaining 15 s and more is EquationSolver.InSolveSystem, which eliminates one
variable at a time using closed-form radical formulas. #860 measured why that does not finish on a
coupled system: each elimination turns the next step's coefficients into nested radicals, so size
compounds multiplicatively per branch.
So Solve bounds its fast path and then hands the problem to an unbounded one.
Why the obvious fix is wrong
GroebnerSystemSolver.TrySolve returns false both when a system is not polynomial over Q and
when it is, but the budget ran out. It is tempting to decline in the second case — the system is
polynomial, the Gröbner engine gave up, and radical elimination is documented not to finish.
That would regress systems that work today:
solvesys[a,b,c,d,e] a^4-1 ; b^4-1 ; c^4-1 ; d^4-1 ; e^4-1
=> all 1024 solutions, quickly
1024 solutions means a quotient dimension of 1024, above GroebnerBudget.MaxQuotientDimension of
512, so the Gröbner path declines — and the eliminator solves it cheaply, because the system is
uncoupled. "Gröbner declined" does not imply "hopeless", and nothing in the return value
distinguishes the uncoupled-but-large case from the coupled-and-swelling one.
The options, as I see them
- Give
InSolveSystema budget and raiseNotSufficientlySupportedExceptionwhen it runs out.
Honest by the ordering in AGENTS.md — no answer beats a slow one — and it makesSolvebounded for
every input rather than for the inputs one path happens to handle. Costs: a second budget to keep
in step with the first, and a behaviour change for anyone currently waiting minutes for an answer
they do get. - Leave it, and treat bounding as the caller's job.
MathS.Multithreading.SetLocalCancellationTokenexists for exactly this and is documented in the
wiki's Multithreading page. Costs nothing, and means the library's own answer to "this may not
finish" is "pass a token". - Bound only where the Gröbner path parsed the system and the coefficients were what swelled —
i.e. distinguish the budget's exit reasons and decline only on the coefficient bound, not on the
quotient-dimension cap. That would keep the 1024-solution case working. It rests on the assumption
that coefficient swell in Buchberger predicts non-termination in the eliminator, which sounds
right and is not measured.
I have not picked one: (1) and (2) are a maintainer's call about what Solve promises, and (3) needs
a measurement nobody has taken. What is not in question is that the present behaviour is the worst of
the three to debug, because the same call is bounded or unbounded depending on which internal path
accepted it.
Activity
Rafael-SOWNet commentedon Aug 11, 2026
Prior art, found while triaging the open pull requests: #610 already attempted option 1, in November 2022.
It added a public
Entity.SimplifyTimeConstrained(level, msLimit)and used it inside the very methodthis issue is about:
— a 500 ms budget per equation before
InSolveSystemstarts eliminating. Neither the API nor the callreached
master; the branch was left as a draft.Two things in it are worth carrying forward, and one worth not:
The shape is right. A time budget expressed as "simplify if you can within this, otherwise hand
back the cheap form" is exactly what the fall-through needs, and returning
nullon exhaustion isthe honest signal AGENTS.md asks for rather than an exception in the common path.
Per-equation rather than per-solve. Time constrained simplificaiton #610 budgets each equation separately, which bounds the
pre-simplification but not the elimination that follows — so it would not by itself have stopped
cyclic-6 from running past 20 s. A budget for this issue has to cover the elimination.
Its change to
ExitIfCancelledshould not be copied. To make the wrapper work it cleared theambient cancellation token from inside the check and threw a bare
OperationCanceledException:Clearing shared ambient state from a predicate would make one timed-out call silently disarm
cancellation for everything else on that context — and the settings scopes have since moved to
following the call rather than the thread, which makes that worse rather than better.
Closing #610 and recording it here so the attempt is not lost with the branch.
Rafael-SOWNet commentedon Aug 11, 2026
A third attempt, older than #610: #377 (2021) added a quota —
Core/QuotaGC/QuotaCounter.csand anOutOfQuotaInterruption— bounding a computation by work done rather than by wall clock.So this problem has been attacked three times in five years and never landed:
SimplifyTimeConstrained(msLimit:)Worth saying because it argues for settling the decision here rather than writing a fourth mechanism:
two exist in git history and neither was rejected on its merits, they were simply left as drafts.
One point in the quota's favour that the time budget cannot match, and which matters for this library
specifically: a quota is reproducible. The same input gives the same answer on a fast machine and a
slow one, so a bounded
Solvestays deterministic and testable. A millisecond budget makes the answerdepend on the machine, which is awkward for a library whose test suite asserts exact expressions — and
it is why the
GroebnerBudgetlimits pairs, basis size, terms, coefficient digits and time ratherthan time alone. Against a quota: the counting has to happen on the hot path.
If option 1 is chosen, the existing
GroebnerBudgetis the model to copy rather than either branch —it already bounds five things, and #860's measurements show the non-time limits are what actually catch
the runaway cases.
Rafael-SOWNet commentedon Aug 16, 2026
Still live on
masterat2d128f3c, and worse than recorded. The issue says cyclic-6 "exceeds 20 s"; I gave it 180 s and it did not finish — no answer, no exception, still running when the harness killed it. So the unbounded path is not merely slow on this input, it is unbounded in the way the title says.Nothing in the three options has changed shape, and (1) and (2) are still a call about what
Solvepromises rather than something to infer.On (3), the one that needs a measurement rather than a decision. The assumption it rests on is that coefficient swell in Buchberger predicts non-termination in the eliminator. That is testable and the experiment is well-defined:
GroebnerSystemSolver.TrySolveto report why it declined — not polynomial, quotient-dimension cap, or coefficient bound — instead of a barefalse;a^4-1 ; … ; e^4-1family that declines on dimension and solves cheaply;If it separates cleanly, (3) is available and keeps the 1024-solution case working. If it does not, (3) collapses into (1) and the choice is genuinely between (1) and (2).
I have not taken that measurement — flagging that it is the thing standing between this issue and a decision, and it is a day's work rather than a design argument. Happy to run it if it is wanted; the instrumentation is small and the corpus is the part that needs care, since the uncoupled-but-large case is the one that must keep working.
Rafael-SOWNet commentedon Aug 16, 2026
I took the measurement. It refutes option 3, which means this reduces to a straight choice between (1) and (2).
I instrumented
GroebnerSystemSolver.TrySolveto record why it declined instead of returning a barefalse, then ran each system through the Gröbner path and, separately, through the wholeSolvewith a 30-second wall clock.masterata45a7256, .NET 10.x^4-1, 5 vars (1024 sols)x^5-1, 5 vars (3125 sols)x^4-1, 4 vars (256 sols)sin(x)+y)x²+y²-4,xy-1)quotient dimensionappears on both sides. It is the reason for two systems the eliminator handles comfortably and for cyclic-4, which it cannot finish in thirty seconds. So the rule option 3 proposes — decline on the coefficient bound, keep going on the dimension cap — does not separate the cases. It would leave cyclic-4 exactly as unbounded as it is today, while still being an extra bound to keep in step.And the coefficient bound never fired at all in this corpus. The bounds that actually trip are the quotient dimension and the time limit. So the assumption option 3 rests on — that coefficient swell in Buchberger predicts non-termination in the eliminator — has no positive instances here to test, let alone confirm.
Two smaller things the run turned up:
Solve, it has to bound that.falseconflates "not a polynomial system" with "polynomial, budget exhausted", and those want opposite responses. I have the instrumentation on a branch and can open it as its own PR if you want it, independently of which option you pick — it is diagnostic only and nothing acts on it.Limits of the measurement. One corpus, one machine, a 30-second cut-off; "no coefficient-bound decline observed" is an absence rather than a proof that one cannot happen. But option 3 needed the reason to separate the cases, and one counter-example is enough to show it does not.
So: (1) give the eliminator a budget and raise
NotSufficientlySupportedException, or (2) leave it toSetLocalCancellationToken. That is a call about whatSolvepromises, and it is yours.Rafael-SOWNet commentedon Aug 22, 2026
A proposal: make the budget a thing the caller can see and set
Coming back to this after being asked, off-issue, for a rule of the shape "don't refuse anything solvable, but let the caller know there is a ceiling and be able to raise it or continue past it." That is a fourth option alongside the three above, and most of it already exists here — just not as one thing, and not visible.
What the library has today
MathS.Settings.MaxExpansionTermCount(2 000),FloatToRationalIterCount(15),MaxAbsNumeratorOrDenominatorValue(10⁸)Setting<T>,AsyncLocal, scoped withusing var _ = ….Set(n)nullinternally; the caller sees a fallback or an unevaluated nodeGroebnerBudget—MaxPairs,MaxBasisSize,MaxTerms,MaxCoefficientDigits,MaxQuotientDimension,Limit = 5 sExceedednames the ceiling that was hitMathS.Multithreading.SetLocalCancellationTokenAsyncLocal, 40 check sites across 17 filesOperationCanceledExceptionGroebnerBudgetis already the design. Named structural ceilings, a wall clock, and a string saying which one gave out — with a docstring explaining why one ceiling would not do ("a system has been seen to give up with 53 pairs and 64 terms and coefficients 188 digits wide, which no count of pairs or terms would have caught"). What is wrong with it is that it isinternal, serves one solver, and nothing outsideBuchberger.csreadsExceeded. The reason is computed and discarded.The state that has no representation
AGENTS.mddistinguishes two outcomes: unevaluated means I could not settle this,NaNmeans this does not exist. A budget running out is a third: this is settleable, given more. Nothing in the library can say it.That is exactly this issue's complaint, stated generally.
GroebnerSystemSolver.TrySolvereturnsfalseboth when a system is not polynomial over ℚ and when it is but the budget ran out — and the post above notes that "Gröbner declined" does not imply "hopeless", with the 1024-solution case to prove it. The information needed to tell those apart is computed and thrown away one frame later.Three increments, smallest first
1 — surface the reason. No new public type. The style already in use here is
AsyncLocal, so a read-only diagnostic in the same shape:Zero signature changes, and it makes option 3 above ("distinguish the budget's exit reasons") implementable — including the assumption it rests on, that coefficient swell in Buchberger predicts non-termination in the eliminator, which the post correctly flags as not measured. With the reason visible that becomes a measurement rather than a guess.
2 — one budget rather than three. Promote
GroebnerBudget's shape to a publicComputationBudgetreachable as aSetting<T>, with a wall clock plus structural ceilings. Gröbner's becomes a specialisation of it, and the unbounded eliminator that this issue is actually about gets one — which is option 1, but with the caller able to raise it instead of being told "no", and able to see that it was a ceiling and not a refusal.3 — continue. Two honest readings, and they cost very differently:
"coefficients", widens that ceiling, calls again. It re-does the work, which for a ceiling you are deliberately raising is usually fine.Entity. Buchberger could do it — its state is an explicit pair queue plus a basis, which is why it has a budget at all — and so could equality saturation.Simplify,IntegrateandLimitare deep recursions with no reifiable state; resuming those means rewriting them as explicit worklists first. I would treat resumability as something individual solvers opt into and advertise, never as a promise on the entry points.What this would settle
Option 2 above ("treat bounding as the caller's job —
SetLocalCancellationTokenexists") stays true and stays useful, but it answers a different question: a token says stop, not how close were we or what would be enough. Under a "don't refuse anything solvable" rule, cancellation alone is the wrong instrument, because the caller learns nothing they can act on.None of this is a decision I should take — it adds public surface, and the shape of (1) in particular is a taste call between an
AsyncLocaldiagnostic and aTrySolve-style API pair. Happy to implement whichever, or to do (1) alone first, since it is additive, needs no new type, and immediately makes the measurement this issue is blocked on possible.A budget that is a value, and a reason that survives the call (#373, #…
Solving a system is bounded whichever internal path takes it (#896) (#…
The tangent, cotangent, secant and cosecant reach the half-angle subs…
The tangent, cotangent, secant and cosecant reach the half-angle subs…