Solving Polynomial Systems by Polyhedral Homotopies
To solve a polynomial system via homotopy continuation methods, one first
constructs a start system whose solutions are known or easier to compute.
Next, continuation methods are applied to track the solution paths from
the known solutions of the start system to the solutions of the system.
A critical factor in the performance of the solver is the number of paths
that must be tracked. A solver that fails to recognize the sparse structure
of a system will end up tracking many diverging solution paths.
Polyhedral homotopies are optimal for systems whose coefficients are
sufficiently generic, as the mixed volume of the Newton polytopes of
the polynomials in the system is then a sharp root count.