Solving systems of polynomial equations is an important problem in mathematics. It has a wide range of applications in many fields of mathematics, sciences, and engineering. By the Abel’s impossibility theorem and Galois theory, explicit formulae for solutions to such systems by radicals are unlikely to exist, as a result, numerical computation arises naturally in the solution to such systems. Homotopy continuation methods represent a major class of numerical methods for solving systems of polynomial equations. The basic idea behind such methods is to deform a hard problem in to an easier problem or into a problem whose solutions are already known, and use the solutions of the easier problem to find those of the harder problem.

Instead of attacking a system of polynomial equations, or simply a polynomial system, head on, the homotopy continuation methods consider it as a member of a family of closely related polynomial systems parametrized by a single real parameter. One member of this family should be trivial to solve, and the solutions of this trivial system should be connected via smooth solution paths to all isolated solutions of the original target system.

Mathematical description

More precisely, to solve a polynomial system of the form $$ P (x) = \begin{cases} p_1 (x_1,\ldots,x_n) &= \sum_{k_1, \ldots, k_n} c^{(1)}_{k_1, \ldots, k_n} x_1^{k_1} \cdots x_n^{k_n} = 0 \\ \vdots &\vdots \\ p_n (x_1,\ldots,x_n) &= \sum_{k_1, \ldots, k_n} c^{(n)}_{k_1, \ldots, k_n} x_1^{k_1} \cdots x_n^{k_n} = 0 \end{cases} $$ we construct a homotopy \(H: \mathbb{C}^n \times [0,1] \to \mathbb{C}^n\) between the given polynomial system \(P\) and some chosen system \(Q\). That is, \(H\) is a continuous map from the product space \( \mathbb{C}^n \times [0,1] \) to \( \mathbb{C}^n \) such that \( H(x,0) \equiv Q(x) \) and \( H(x,1) \equiv P(x)\).

Basics of path tracking

Different homotopy constructions