How Parameter Homotopy works

Originating from what is called the Cheater's Homotopy [1] the

Paramotopy uses a superior method, the Coefficient-Parameter Homotopy, coming from Morgan and Sommese [2].

*parameter homotopy*is a method for repeatedly solving a parametrized polynomial system.Paramotopy uses a superior method, the Coefficient-Parameter Homotopy, coming from Morgan and Sommese [2].

Step 1

First, you need to solve the system at a

*generic*parameter point $p_0$. Generic means that the parameter values are chosen by a trusted random number generator, and that the values lie in the complex numbers $\mathbb{C}^n$. Then Bertini's Theorem dictates that we will find the full number of isolated solutions at this generic point.In Paramotopy, the solver Bertini tracks the system through time and space to find the solutions to the problem, at the generic parameter point $p_0$. The start system is constructed by Bertini, and typically is the total degree homotopy, although other methods may be used to obtain the generic solutions, such as regeneration.

The result of Step 1 is a full set of generic solutions to the system at $p_0$.

The result of Step 1 is a full set of generic solutions to the system at $p_0$.

Step 2

Paramotopy was built for Step 2. Using the solutions from Step 1, Bertini tracks solutions from $p_0$ to all desired parameter values. Because we have

*all*solutions at the generic point, we are guaranteed to obtain*all*solutions at each parameter point.The benefit of using a parameter homotopy is time and computation savings. Whereas the initial solve may have tens of thousands of paths to track, each parameter point may have only a dozen solutions. For almost all systems, performing a fresh homotopy for each parameter point would take

*substantially*longer than leveraging genericity of solutions from Step 1. Hence, Paramotopy.References:

[1] Li, T., Sauer, T., and Yorke, J. "The Cheater’s Homotopy: An Efficient Procedure for Solving Systems of Polynomial Equations."

[2] Morgan, Alexander P., and Andrew J. Sommese. "Coefficient-parameter polynomial continuation."

[1] Li, T., Sauer, T., and Yorke, J. "The Cheater’s Homotopy: An Efficient Procedure for Solving Systems of Polynomial Equations."

*SIAM Journal on Numerical Analysis*26:5 (1989): 1241-1251.[2] Morgan, Alexander P., and Andrew J. Sommese. "Coefficient-parameter polynomial continuation."

*Applied Mathematics and Computation*29.2 (1989): 123-160.