# Polyhedral homotopy

A start system from polyhedral geometry

### Polyhedral start systems

Polyhedral is a particular choice of start system for homotopy continuation.

The advantage of so called polyhedral homotopies over total degree homotopies is that the number of paths to track can be significantly smaller for the polyhedral homotopy.

Here is how it works:

julia> using HomotopyContinuation, PolynomialTestSystems
julia> f = equations(cyclic(7))
julia> solve(f; start_system = :polyhedral)
Result with 924 solutions
==================================
• 924 non-singular solutions (56 real)
• 0 singular solutions (0 real)
• 924 paths tracked
• random seed: 606778


For comparison:

julia> solve(f; start_system = :total_degree)
Result with 924 solutions
==================================
• 924 non-singular solutions (56 real)
• 0 singular solutions (0 real)
• 5040 paths tracked
• random seed: 286291


The number of paths for the total degree start system is 5040, while for the polyhedral homotopy it is only 924.

The underlying idea goes back to Huber and Sturmfels. In our implementation we use Anders Jensen's algorithm for the computation of the mixed cells.

### Solutions with non-zero entries

If it is known that all of the solutions of the system have non-zero entries (i.e., that they are points in $(\mathbb{C}\backslash\{0\})^n$), then one can accelerate the computation as follows:

solve(f; start_system = :polyhedral, only_torus = true)


Here is an example:

@var x y
f = System([2y + 3y^2 - x*y^3, x + 4*x^2 - 2*x^3*y])
solve(f, start_system=:polyhedral, only_torus=true)

Result with 3 solutions
=======================
• 3 paths tracked
• 3 non-singular solutions (3 real)
• random seed: 0x07df8713
• start_system: :polyhedral


whereas

solve(f, start_system=:polyhedral, only_torus=false)

Result with 6 solutions
=======================
• 8 paths tracked
• 6 non-singular solutions (6 real)
• random seed: 0x60ae238f
• start_system: :polyhedral