The Homotopy(eqns, options) function finds isolated non-repeated roots of square systems of polynomial equations (that is, the zeros of the polynomials in eqns), returning them as a list.

Homotopy attempts to find all isolated multiplicity one roots for the system of equations 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.

For an input system $\left\{p_1\left(x_1\,x_2\,\dots \,x_n\right)\,\dots \,p_n\left(x_1\,x_2\,\dots \,x_n\right)\right\}$ and automatically generated random start system $\left\{q_1\left(x_1\right)\,\dots \,q_n\left(x_n\right)\right\}$, this map is of the form $H\left(x\,t\right)\=\left\{\left(1-{\left(1-t\right)}^2\right)p_1\left(x_1\,x_2\,\dots \,x_n\right)-{\left(1-t\right)}^2{q}_1\left(x_1\right)\,\dots \,\left(1-{\left(1-t\right)}^2\right)p_n\left(x_1\,x_2\,\dots \,x_n\right)-{\left(1-t\right)}^2{q}_n\left(x_n\right)\right\}$, which is called the homotopy system. When $t=0$, solutions of $H\left(x\,0\right)$ are solutions of the generated system, and when $t=1$, solutions of $H\left(x\,1\right)$ are solutions of the input system.

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

Homotopy then differentiates the homotopy system, turning the problem into the integration of an ODE system over $t=0..1$. 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 $t=0..1$, and by default has a value of M=400. As an option, M must be in the range $10..\mathrm{\infty }$.

MinimumStepSize = m controls the smallest step that can be taken on any path before abandoning it. The default value is $1.\times {10}^{\mathrm{-7}}$, but can be set in the range $1.\times {10}^{\mathrm{-9}}..0.001$. The smaller the value, the harder Homotopy works.

Tolerance = tol is used as a partial criterion throughout the computation of a path for when the correction steps have sufficiently converged. It also has a second purpose, which is to provide a strict limit for the accuracy of the output isolated roots, in that these should satisfy the normalized input polynomials (that is, each polynomial is divided by the modulus of its largest coefficient) to within a maximum error of tol. The default value is $1.\times {10}^{\mathrm{-8}}$, but it can be set in the range $1.\times {10}^{\mathrm{-14}}..0.0001$. There is an additional constraint that the tolerance value $\mathrm{tol}$ must be smaller than 1/10 the minimum step size m.

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.

$\mathrm{with}\left(\mathrm{RootFinding}\right)$

$\left[\mathrm{Analytic}\,\mathrm{AnalyticZerosFound}\,\mathrm{BivariatePolynomial}\,\mathrm{EnclosingBox}\,\mathrm{EvaluateAtRoot}\,\mathrm{HasRealRoots}\,\mathrm{Homotopy}\,\mathrm{Isolate}\,\mathrm{NextZero}\,\mathrm{Parametric}\,\mathrm{RefineRoot}\,\mathrm{WitnessPoints}\right]$

$\mathrm{Homotopy}\left(\left[25xy-11\,x^2+y^2-1\right]\right)$

$\left[\left[x=\mathrm{-0.5123603793}-0.\mathrm{I}\,y=\mathrm{-0.8587705408}+0.\mathrm{I}\right]\,\left[x=\mathrm{-0.8587705415}-0.\mathrm{I}\,y=\mathrm{-0.5123603786}+0.\mathrm{I}\right]\,\left[x=0.8587705415+0.\mathrm{I}\,y=0.5123603786-0.\mathrm{I}\right]\,\left[x=0.5123603793+0.\mathrm{I}\,y=0.8587705408-0.\mathrm{I}\right]\right]$

$\mathrm{sys}≔\left\{\mathrm{randpoly}\left(\left[u\,v\right]\,\mathrm{degree}=2\right)\,\mathrm{randpoly}\left(\left[u\,v\right]\,\mathrm{degree}=3\right)\right\}$

$\mathrm{sys}≔\left\{-62u^2+97uv-73v^2-56u+87\,71u^3-17u{v}^2+80u^2-44v^2+62u-82v\right\}$

$\mathrm{sols1}≔\mathrm{Homotopy}\left(\mathrm{sys}\right)$

$\mathrm{sols1}≔\left[\left[u=\mathrm{-0.2140065340}-0.7500992223\mathrm{I}\,v=\mathrm{-1.406179676}-0.6741681736\mathrm{I}\right]\,\left[u=0.8468475365-0.\mathrm{I}\,v=1.062243147-0.\mathrm{I}\right]\,\left[u=\mathrm{-0.2140065344}+0.7500992219\mathrm{I}\,v=\mathrm{-1.406179676}+0.6741681732\mathrm{I}\right]\,\left[u=\mathrm{-1.069439412}+0.\mathrm{I}\,v=\mathrm{-1.953758199}+0.\mathrm{I}\right]\,\left[u=\mathrm{-1.064544629}-0.8455148939\mathrm{I}\,v=0.6487441050-0.5933444492\mathrm{I}\right]\,\left[u=\mathrm{-1.064544629}+0.8455148939\mathrm{I}\,v=0.6487441050+0.5933444492\mathrm{I}\right]\right]$

$$\begin{gathered} \mathbf{for}i\mathbf{in}\mathrm{sols1}\mathbf{do} \\ \mathrm{evalf}\left[20\right]\left(\mathrm{eval}\left(\mathrm{sys}\,i\right)\right) \\ \mathbf{end}\mathbf{do} \end{gathered}$$

$\left\{\mathrm{-6.465266131}\times {10}^{\mathrm{-8}}-2.0357009682\times {10}^{\mathrm{-8}}\mathrm{I}\,3.6448225044\times {10}^{\mathrm{-8}}+1.8841671843\times {10}^{\mathrm{-8}}\mathrm{I}\right\}$

$\left\{\mathrm{-4.9664346603}\times {10}^{\mathrm{-8}}+0.\mathrm{I}\,3.20577096702\times {10}^{\mathrm{-7}}+0.\mathrm{I}\right\}$

$\left\{4.75657086\times {10}^{\mathrm{-9}}+1.0616556201\times {10}^{\mathrm{-8}}\mathrm{I}\,8.1478504576\times {10}^{\mathrm{-8}}-1.5266867773\times {10}^{\mathrm{-8}}\mathrm{I}\right\}$

$\left\{\mathrm{-1.770939873}\times {10}^{\mathrm{-8}}+0.\mathrm{I}\,\mathrm{-1.358429716}\times {10}^{\mathrm{-8}}+0.\mathrm{I}\right\}$

$\left\{1.21639664\times {10}^{\mathrm{-9}}+1.31210215858\times {10}^{\mathrm{-7}}\mathrm{I}\,6.664198762\times {10}^{\mathrm{-8}}+2.3924219086\times {10}^{\mathrm{-8}}\mathrm{I}\right\}$

$\left\{1.21639664\times {10}^{\mathrm{-9}}-1.31210215858\times {10}^{\mathrm{-7}}\mathrm{I}\,6.664198762\times {10}^{\mathrm{-8}}-2.3924219086\times {10}^{\mathrm{-8}}\mathrm{I}\right\}$

$\mathrm{sols2}≔\mathrm{Homotopy}\left(\mathrm{sys}\,\mathrm{Tolerance}=1.\times {10}^{\mathrm{-12}}\right)$

$\mathrm{sols2}≔\left[\left[u=\mathrm{-0.2140065347}+0.7500992219\mathrm{I}\,v=\mathrm{-1.406179677}+0.6741681731\mathrm{I}\right]\,\left[u=\mathrm{-1.064544629}+0.8455148939\mathrm{I}\,v=0.6487441050+0.5933444492\mathrm{I}\right]\,\left[u=\mathrm{-1.069439412}+0.\mathrm{I}\,v=\mathrm{-1.953758199}+0.\mathrm{I}\right]\,\left[u=0.8468475356-0.\mathrm{I}\,v=1.062243147+0.\mathrm{I}\right]\,\left[u=\mathrm{-0.2140065347}-0.7500992219\mathrm{I}\,v=\mathrm{-1.406179677}-0.6741681731\mathrm{I}\right]\,\left[u=\mathrm{-1.064544629}-0.8455148939\mathrm{I}\,v=0.6487441050-0.5933444492\mathrm{I}\right]\right]$

$$\begin{gathered} \mathbf{for}i\mathbf{in}\mathrm{sols2}\mathbf{do} \\ \mathrm{evalf}\left[20\right]\left(\mathrm{eval}\left(\mathrm{sys}\,i\right)\right) \\ \mathbf{end}\mathbf{do} \end{gathered}$$

$\left\{\mathrm{-5.5873201710}\times {10}^{\mathrm{-8}}+2.33098301\times {10}^{\mathrm{-10}}\mathrm{I}\,\mathrm{-1.333952708}\times {10}^{\mathrm{-8}}-8.54076131\times {10}^{\mathrm{-10}}\mathrm{I}\right\}$

$\left\{1.21639664\times {10}^{\mathrm{-9}}-1.31210215858\times {10}^{\mathrm{-7}}\mathrm{I}\,6.664198762\times {10}^{\mathrm{-8}}-2.3924219086\times {10}^{\mathrm{-8}}\mathrm{I}\right\}$

$\left\{\mathrm{-1.770939873}\times {10}^{\mathrm{-8}}+0.\mathrm{I}\,\mathrm{-1.358429716}\times {10}^{\mathrm{-8}}+0.\mathrm{I}\right\}$

$\left\{2.510011687\times {10}^{\mathrm{-9}}+0.\mathrm{I}\,2.2617168569\times {10}^{\mathrm{-8}}-0.\mathrm{I}\right\}$

$\left\{\mathrm{-5.5873201710}\times {10}^{\mathrm{-8}}-2.33098301\times {10}^{\mathrm{-10}}\mathrm{I}\,\mathrm{-1.333952708}\times {10}^{\mathrm{-8}}+8.54076131\times {10}^{\mathrm{-10}}\mathrm{I}\right\}$

$\left\{1.21639664\times {10}^{\mathrm{-9}}+1.31210215858\times {10}^{\mathrm{-7}}\mathrm{I}\,6.664198762\times {10}^{\mathrm{-8}}+2.3924219086\times {10}^{\mathrm{-8}}\mathrm{I}\right\}$

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

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