RootFinding[Homotopy]  find numerical approximations to roots of systems of polynomial equations

Calling Sequence


Homotopy(eqns, options)


Parameters


eqns



set or list of polynomial equations or polynomials

options



(optional) equations of the form option=value where option is one of MaxPredictorSteps, MinimumStepSize, or Tolerance; control solution method





Description


•

The Homotopy(eqns, options) function finds isolated nonrepeated roots of square systems of polynomial equations, returning them as a list.


Homotopy attempts to find all isolated multiplicity one roots for the system of equations eqns that are not part of a solution manifold.

•

The basic concepts used by the algorithm are straightforward.


Computation of the roots is by a homotopy, which is a continuous map from a set of known solutions to the solutions of the input system. The known solutions are generated by Homotopy from a simple random start system.


Once this map is created, then follow each path from a known solution to a possible solution of the input system by varying from 0 to 1.


Homotopy then differentiates the homotopy system, turning the problem into the integration of an ODE system over . The path is then followed by discrete steps, using an ODE solution method as a predictor for each step, and an application of Newton's method as a corrector for each step, thus ensuring the computed solution stays on the path.

•

Potential difficulties include paths that are close at some time, or isolated roots that are close. The default for Homotopy is to compute the roots that it can obtain easily, and stop for more expensive roots indicating that the computation becomes too difficult for the current settings. These settings can be controlled through a number of options.

•

MaxPredictorSteps = M controls the maximum number of steps taken from , and by default has a value of M=400. As an option, M must be in the range .

•

MinimumStepSize = m controls the smallest step that can be taken on any path before abandoning it. The default value is , but can be set in the range . The smaller the value, the harder Homotopy works.

•

In summary, the default settings are sufficient for many problems, but for difficult problems a combination of increasing the maximum number of predictor steps and decreasing the minimum step size and tolerance may produce the desired solutions when the default values are insufficient.

•

In addition, for cases in which only a few solutions are needed, these can be obtained more efficiently by increasing the minimum step size and tolerance.



Examples


>


 (1) 
Intersection points of a line and circle:
>


 (2) 
Random system:
>


 (3) 
>


 (4) 
>


 (5) 
Tighter tolerance:
>


 (6) 
>


 (7) 
>




References



Allgower, E.L., and Georg, K. "Numerical path following." Handbook of Numerical Analysis, Vol. 5. NorthHolland, 1997.


Verschelde, J. "Algorithm 795: PHCpack: A generalpurpose solver for polynomial systems by homotopy continuation." Transactions on Mathematical Software, Vol. 25, No. 2 (1999): 251276.


