Following a root from a problem already solved

There is a method for solving polynomial systems that sounds, on first hearing, like a joke.

Do not solve the system. Solve a different system — one whose answers can be written down without any work at all — and then slowly turn that system into the one that was wanted, keeping hold of every answer as it slides. When the deformation is finished, the answers being held are the answers to the original problem.

It is called homotopy continuation, it is how the counts in this field are obtained, and the reason it is not a joke is that it is complete. A method that starts holding all of the easy problem’s solutions ends holding all of the hard one’s. Nothing is searched for, so nothing can be missed.

The easy problem #

The system that gets deformed is called the start system, and it is chosen for one property: its solutions are obtainable by inspection.

If the target system has equations of degrees $d_1, d_2, \ldots, d_n$, the start system is

$$x_1^{d_1} - c_1 = 0, \quad x_2^{d_2} - c_2 = 0, \quad \ldots$$

for constants $c_i$. Each equation involves one unknown and says it is a $d_i$-th root of a number, so its solutions are the $d_i$ roots of unity scaled and rotated — written down, not computed. Every combination of one root from each equation is a solution of the whole system, and there are $d_1 d_2 \cdots d_n$ of them.

That product is Bézout’s number. So the start system has exactly as many solutions as the target can have, which is the whole trick: a bijection is available before either system has been solved.

For the four-bar, both equations are quadratic, so the start system is $x^2 = c_1$, $y^2 = c_2$ — four solutions, and four paths. For a Gough platform in space, six cubics and a quadratic give 1,458.

The deformation #

Write $G$ for the start system and $F$ for the target, and consider

$$H(z, s) = (1 - s)\,\gamma\,G(z) + s\,F(z).$$

At $s = 0$ this is $\gamma G$, whose solutions are known. At $s = 1$ it is $F$. In between it is a system of the same shape with coefficients sliding from one to the other.

Each of the start solutions is followed as $s$ runs from 0 to 1. The following is done in small steps: predict where the solution has moved using the derivative $\mathrm{d}z/\mathrm{d}s = -J^{-1}\,\partial H/\partial s$, then correct with a couple of Newton iterations at the new $s$. If the correction fails, the step is halved; after three successes in a row it is doubled.

That is the entire algorithm, and its correctness rests on one thing: the path must not run into a singularity.

A singularity is a value of $s$ at which two of the paths meet, or at which the Jacobian $J$ becomes singular so that there is no well-defined direction to move in. A path that meets one either dies or — much worse — is picked up on the far side by the corrector and continued as some other path. Two paths merge, one solution gets counted twice, and one is silently lost.

Nothing about the arithmetic complains when this happens. The endpoint is a genuine solution of $F$, refined to $10^{-13}$; it is simply not the one that path was carrying.

Why the deformation is complex #

Here is the argument that makes the method work, and it is one of the more elegant things in this subject.

The set of coefficient vectors for which a system has a singular solution is itself defined by a polynomial equation — the discriminant. So the bad systems form a hypersurface in the space of coefficients: something of codimension one.

Now, a straight-line path from $G$ to $F$ with real coefficients is a one-real-dimensional path in a real space, and a one-dimensional path in a real space meets a codimension-one hypersurface all the time. Generic real lines hit it.

Make the parameter complex and everything changes. The path $s \mapsto H(\cdot, s)$ for $s$ running along a segment is still one-dimensional, but the bad set now has real codimension two — a complex hypersurface is two real dimensions down — and a one-dimensional path misses a two-codimensional set with probability one.

That is why the coefficients are complex. Not because the answers are complex, though some of them are, but because a path through complex coefficient space can go around the systems that would kill it, and a path along the real axis has to go through them.

The trick, and what it is a trick for #

The γ in the formula is a random complex number of modulus one, and it has a name — the γ-trick — and a standard telling. The telling is that without it the deformation runs along the real axis, and with it the deformation is generic, so γ is what makes the method work.

That is an assertion about what happens when γ is removed, and this site’s habit is that an assertion which has never rejected anything proves nothing. So it was removed.

The first version of the check ran the tracker with γ and with $\gamma = 1$, and required the second to be worse. It failed on every system here. With $\gamma = 1$ the tracker found all six solutions of the platform, all four of Burmester’s five-position system, both of the four-bar’s — from every seed tried.

The check was right to fail. The sentence it was checking was folklore.

Where the randomness actually lives #

The reason γ was not needed is that the start system’s constants $c_i$ were already complex, and they are just as much a source of genericity. The path from $\gamma G$ to $F$ is one line in coefficient space; whether it avoids the discriminant depends on the whole line, and randomising either end randomises the line.

There are therefore two places the genericity can come from, and the honest experiment is to run all four combinations.

Three of the four corners are complete. The fourth — γ = 1 and real start constants, the configuration in which nothing anywhere is complex except the arithmetic — finds two of six on the platform, and one of four on Burmester’s system, from every seed.

So the correct statement is not that γ is magic. It is that the deformation has to be generic, and there is more than one way to pay for that. γ is one; complex start constants are another; either alone suffices; removing both is what breaks it.

assertTheRandomnessIsLoadBearing now measures all four corners and requires exactly that pattern — three complete, one not. It is a stronger claim than the one it replaced and it is the one that survives contact with the measurement.

The system that cannot demonstrate any of it #

There is a second half to that check, and it is a refusal.

The four-bar finds both of its solutions in all four corners. It cannot demonstrate the claim at all, and assertTheRandomnessIsLoadBearing fails when it is pointed at one — with the message that the system is too small to show that the path has to be generic.

That is deliberate. A demonstration needs a system big enough to have a path collision available, and two circles do not: their four paths are two that arrive and two that leave for the circular points, and there is nothing for anything to collide with. Running the experiment on the smallest example and reporting that the precaution was unnecessary would have been a perfectly reproducible way of reaching the wrong conclusion.

The smallest example is the wrong one, and it is the wrong one for a stateable reason rather than by bad luck. That is worth having in the check.

The predictor is allowed to be wrong #

One detail of the tracker is worth pulling out, because it looks like sloppiness and is not.

The step direction needs $\partial H/\partial s$. For the total-degree homotopy that derivative is exactly $F - \gamma G$, because $H$ is linear in $s$ — so it is available in closed form and costs nothing. For a homotopy that walks a mechanism’s parameters rather than its coefficients, the dependence is not linear, and the derivative is taken by a central difference.

A finite difference in the middle of an otherwise exact method sounds like a compromise. It is not, because of what the predictor is for: it decides where the corrector starts, and the corrector is exact. A bad tangent costs a halved step. It cannot cost a wrong answer.

What can cost a wrong answer is a corrector that converges to the wrong root, which is the collision described above — and that is a question about step size and genericity, not about the tangent’s accuracy. So the effort goes where the risk is: the step control is adaptive, the endpoint is polished with a tighter tolerance than the path was tracked at, and the tangent is whatever is cheapest.

The finite difference is taken over the coefficient vector rather than by re-evaluating the polynomials, which matters for a different reason. The first version of this library rebuilt the entire polynomial system four times per step — at $s$, at $s \pm \epsilon$, and at the step’s end — and on the Gough platform that took 71 seconds. A homotopy does not change its monomials; only its coefficients move. Compiling the exponents once and treating the coefficients as a separate vector took the same run to 5.2 seconds, with byte-identical answers.

That is a tenfold difference produced by noticing which part of the object was constant, and it is the difference between a figure the build can afford and one it cannot.

What a path looks like #

The paths are worth looking at, because their shape is not what the description suggests.

A start solution sits on a circle of modulus around one, placed by a root of unity. The target solutions sit wherever the mechanism puts them. In between, the path does not travel in anything like a straight line: it loops, doubles back, and spends most of its length nowhere near either end. Two paths can pass within a fraction of a unit of one another and then separate, and it is precisely those near-approaches that the step control exists for — the corrector has to be started close enough to the right root that it cannot fall into the wrong one.

Drawing them is only possible for the smallest systems, and that is an honest limit rather than a presentational one. The platform’s paths live in four complex dimensions; the figures above project them onto the plane of one unknown, which means two paths that appear to cross may be nowhere near each other in the full space. A projection cannot be read as a picture of collisions. What it can be read as is a picture of fates: which paths settle and which leave.

For a Gough platform none of this is drawable at all. Seven complex dimensions, 1,458 paths, and any projection is decoration. Above the smallest examples the only thing to look at is the count.

The end of the path is its own problem #

At $s = 1$ the deformation is over and the path is sitting on a solution — usually. Two things can be true instead, and both need handling.

The path may be heading for infinity. Bézout’s number counts intersections in projective space, and some of them are on the line at infinity, where a mechanism cannot be. Those paths do not fail; they wander, their coordinates grow, the corrector keeps succeeding, and they never settle. Left alone they grind down to a minimum step size and give up after hundreds of iterations, which on the Gough platform is four fifths of the run time for no information at all. Abandoning a path once its norm passes a threshold is what makes the complete route affordable, and the paths that leave is about how large that fraction is.

The solution may be singular. If the target system has a double root, two paths arrive at the same place, and neither of them converges quadratically at the end — Newton on a double root halves the error instead of squaring it. The endpoints still land close enough to be recognised as the same solution, and the pair is reported as one solution of multiplicity two, which is the right answer: a mechanism whose two assemblies have merged is at a singularity, and there is one configuration there, not two.

Distinguishing “two paths arrived at one solution” from “two paths arrived at two solutions ten to the minus seven apart” is a real difficulty and this library does not solve it in general. It polishes every endpoint to a tighter tolerance than the path was tracked at, and compares endpoints after polishing rather than before, which handles the cases that arise here and would not handle a system deliberately constructed to be nasty.

What this is not #

Homotopy continuation is not the only way to count the solutions of a polynomial system, and it is worth saying what the alternatives are, because they have a property this method lacks.

Elimination — resultants, Gröbner bases — is exact. It manipulates the polynomials symbolically until one of them involves a single unknown, and the degree of that polynomial is the count, proved rather than measured. This is where the Gough platform’s classical forty comes from: an elimination, done once, by people who published it.

The trouble is cost. Elimination on seven unknowns with the coefficients left symbolic produces expressions that grow beyond anything usable, and doing it with the coefficients numeric answers the question for one mechanism rather than for the family. It is a different instrument for a different question, and for a site that wants a figure recomputed at build time from whatever arguments a placement passes, it is the wrong one.

So the trade is explicit. Elimination gives a proof about a family; continuation gives a measurement about a member, with a probability-one theorem behind it and a numerical implementation in front of it. This field takes the second and then checks it against every independent thing available — the closed form where one exists, the classical count where one is published, a known symmetry of the equations, and a second numerical method.

That is not as good as a proof. It is what this site can honestly build, and stating which of the two it is doing is most of the point.

What is being trusted #

It is worth setting out plainly what this method does and does not guarantee, because the rest of the field leans on it hard.

It guarantees, with probability one, that every isolated solution of the target is the endpoint of some path. That is a theorem, and it is what makes the count complete rather than a lower bound.

It does not guarantee that the numerics followed those paths correctly. Probability one is a statement about the random choices, not about step sizes and rounding. A path can still be lost to a step that was too large near a near-collision.

So the count is checked by redundancy rather than by certificate:

• Every path is accounted for. Bézout’s number is known in advance, and each path converges, leaves, or fails; the three add up.
• A symmetry the system is known to have must show up in the answers. The platform’s solutions must come in ± pairs, so the count must be even — and that check has already caught a run that returned 79.
• The whole count is compared against a second method that works differently. That is monodromy, and the comparison turned out to be more useful in the other direction than expected.

Two circles meeting twice needed none of this. Everything above it does, and the honest position is that the numbers in this field are as good as the checks around them rather than as good as the theorem behind them.