Finite Root Generation

Finite Root Generation (FRG) is a method to collect all roots of a polynomial system.  Particularly, FRG is useful for solving large systems of equations associated with mechanism synthesis problems.  It uses homotopy continuation to accomplish this goal.

Homotopy continuation finds all roots (endpoints) of a target system by first constructing a start system from which all roots (startpoints) are readily obtainable.  Then the start system is deformed into the target system and each startpoint is tracked to an endpoint, transforming the task of algebraic root finding into solving several independent ordinary differential equations.

In the case of multihomogeneous homotopy, each equation of the start system is a product of linear expressions.  In this way, each startpoint is generated by setting one linear expression from each equation equal to zero and solving the resulting linear system.  Constructing all startpoints involves exhaustively going through these combinations, leading to characteristic explosion.

For the synthesis systems we are interested, the large majority of these startpoints track to endpoints at infinity.  This is due to a degeneration in monomial structure from start system to target system, and these infinite roots serve no purpose but to be filtered out.  Consider the four-bar nine point path generator problem below.

Multihomogeneous homotopy:

(1) The combinatorics generate 286,720 startpoints, of which 97% track to roots at infinity.  (2) Once the set of 8,652 finite roots is found, this data may be used again and again to find finite root sets of other systems with the same monomial structure (3).  This is the standard approach in homotopy continuation: splitting the problem into a computationally expensive ab initio solve followed by cheaper reproduction from the resulting data.

The goal of FRG is to avoid tracking all roots at infinity.  The method accomplishes this, but with a trade-off: startpoints are guaranteed to track to finite roots, but are generated using a stochastic process that may track to the same nonsingular endpoint more than once.  Before getting into the algorithm, let’s examine the implications of this process.

For our benchmark problem, let’s assume that with each iteration of FRG, the algorithm might happen upon one of any of the 8,652 finite roots with equal probability.  In the beginning, the algorithm would always be finding new roots, as the chances of randomly finding one of the 8,652 roots multiple times in a small number of iterations is quite low.  But as more and more roots are collected, the likelihood of finding a previously collected root increases.

This rate of duplication is modeled nicely by a classical problem in probability theory: the coupon collector problem.  This allows us to model the expected relationship between FRG iterations and the number of unique roots collected.  We apply this model to the benchmark problem.

Collecting 95% of the finite root set:

(1) Only 25,922 startpoints need to be constructed to find 95% of the finite root set, that is 91% less homotopy paths to track compared to multihomogeneous homotopy.  The resulting finite roots (2), although incomplete, can be used to find 95% of finite roots for other systems (3) with the same monomial structure.

Collecting 100% of the finite root set:

Repeating this exercise for finding 100% of roots indicates a situation of diminishing returns: 83,430 paths must tracked to find all roots.  Nonetheless, this is 71% less computation compared to multihomogeneous homotopy.

Algorithmically, FRG differs from traditional homotopy in that instead of tracking all startpoints of a single start system, it tracks a single startpoint for multiple start systems.  Start systems and startpoints are generated by first randomly generating a mechanism.  The parameters of the mechanism construct a startpoint, and its motion constructs a start system.  Conducting a parameter homotopy tracks this startpoint to a guaranteed finite endpoint.  Then the endpoint is checked whether it is new or a duplicate, and the algorithm continues until a sufficient number of unique roots have been collected.

FRG represents a significant reduction in computation which should lead to the solution of larger synthesis problems and increase our design capabilities.  Furthermore, by keeping track of the duplication rate, the algorithm accommodates in-process estimations of the size of a root set before it is found.

Homotopy and Mechanism Design

Planar, spherical, and spatial linkage design requires the formulation of synthesis equations. These equations are often polynomials or can be converted to polynomials. The degree of these polynomial systems increases rapidly with mechanism complexity. For example, the synthesis equations of a planar RR constraint used to construct a four-bar linkage that reaches its maximum of five positions is of degree 4. Meanwhile, the lowest computed degree of the synthesis equations for the Watt I six-bar that reaches its maximum of eight positions is 34 billion. See Plecnik et. al.

Resultant methods are unable to keep up with this increase in complexity and optimization methods do not provide a complete solution set. Homotopy continuation and interval analysis are methods capable of providing complete or practical sets of solutions. My research focuses on the former.

 

In particular, the polynomial continuation software Bertini provides an efficient module for solving high degree systems. Using the High Performance Computing cluster at UC Irvine, we have computed systems of degree 4 million. The degree of a system is equal to the number of homotopy paths a computer is required to track. Tracking millions of paths is computationally expensive. As well, kinematics equations tend to have a sparse monomial structure, indicating that the number of roots is actually much smaller than the Bezout and multihomogeneous bounds compute. If all the roots for a system with a given monomial structure can be found once, those results can be used to construct parameter homotopies which can be used to efficiently solve systems of the same structure in the future. In short, a polynomial system would require one big initial solve (on the order of hours/days), and then all future solve are computed quickly (on the order of minutes).

M. Plecnik, J. M. McCarthy, and C. W. Wampler, 2014. “Kinematic synthesis of a Watt I six-bar linkage for body guidance,” Advances in Robot Kinematics. Springer International Publishing, 317-325.

D. J. Bates, J. D. Hauenstein, A. J. Sommese, and C. W. Wampler, 2013. Numerically Solving Polynomial Systems with Bertini. SIAM Books, Philadelphia, PA.

Synthesis of Six-bars

The six-bar linkage is the next simplest 1-DOF planar mechanism after the four-bar. However, designing these mechanisms presents a challenging set of synthesis equations. For example, a four-bar motion generator is determined by a polynomial system that has 4 isolated roots (of which one is the origin), where each root represents a potential design. On the other hand, a six-bar function generator is determined by a polynomial system that could have as many as 4.13×108 roots. Chances are the actual number of roots of this system is much smaller (by 2 or 3 magnitudes), but that number is unknown. It is much harder to find complete solution sets for general six-bar design problems than it is for four-bars.

From a practical point of view, six-bars have 2 more moving parts than four-bars. With the increased complexity comes advantages:

1. More design options. As mentioned above, each root above represents a design candidate, and surely it is better to have thousands of design candidates than 3. Especially because most of these design candidates will suffer from linkage defects rendering them useless.

2. Six-bars do more complex stuff. Four-bars can move through 5, 5, and 9 positions for function, motion, and path generation, respectively. On the other hand, six-bars can move through 11, 8, and 15 positions. The maximum degree of the curve traced by a point on the coupler link of a four-bar versus a six-bar is 6 to 18. Six-bars have even been designed that can perform 2:1 gear ratios.

3. You can put things where they need to be. That is there is much more design freedom shaping links and choosing the locations of pivots. This is useful if your linkage needs to mount to specific hard points or fit within a certain envelope. Four and six-bar motion generators provide a good example. There will be a maximum of 6 four-bars that move through 5 task positions with no pivots specified. Meanwhile, there will be a maximum of 5,735 six-bars that move through 6 task positions with both ground pivots specified!

Here is a bit on my research with six-bars. Six-bars are divided into 5 kinematic inversions. For simplicity, we’ll just call these types. There are three common motion requirement tasks. The table below provides a breakdown of the size of the synthesis problem for each linkage type over the three motion tasks.

This table shows six-bar info

Function Motion Path
Watt I Max positions: 5
Degree: 4
Max positions: 8
Degree: 3.43×1010
Max positions: 15
Degree: 2.28×1046
Watt II Max positions: 11
Degree: 5.50×107
Max positions: 5
Degree: 4
Max positions: 9
Degree: 268,720
Stephenson I Max positions: 5
Degree: 4
Max positions: 5
Degree: 4
Max positions: 15
Degree: ?
Stephenson II Max positions: 11
Degree: 4.13×108
Max positions: 5
Degree: 4
Max positions: 15
Degree: ?
Stephenson III Max positions: 11
Degree: 4.13×108
Max positions: 5
Degree: 4
Max positions: 15
Degree: ?