Edit on GitHub

Homotopies

A homotopy is a function

\[H: \mathbb{C}^N × \mathbb{C} → \mathbb{C}^n, (x,t) ↦ H(x,t)\]

where $H(⋅, t)$ is a polynomial system for all $t∈\mathbb{C}$.

Default homotopies

The following homotopies are available by default

HomotopyContinuation.ParameterHomotopy — Type
ParameterHomotopy(F, parameters;
    variables=setdiff(variables(F), parameters),
    p₁=randn(ComplexF64, length(parameters)),
    p₀=randn(ComplexF64, length(parameters)),
    γ₁=nothing, γ₀=nothing)

Construct the homotopy

\[H(x, t) = F(x, (tγ₁p₁+(1-t)γ₀p₀) / (tγ₁+(1-t)γ₀)),\]

where p₁ and p₀ are a vector of parameter values for $F$ and γ₁ and γ₀ are complex numbers. If γ₁ or γ₀ is nothing, it is assumed that γ₁ and γ₀ are $1$. The input $parameters$ specifies the parameter variables of $F$. Neccessarily, length(parameters) == length(p₁) == length(p₀).

Note that p₁ and p₀ are stored as a tuple p of SVectors and γ₁ and γ₀ are stored as a tuple γ or as γ=nothing

ParameterHomotopy(F, parameters;
    variables=setdiff(variables(F), parameters),
    start_parameters=randn(ComplexF64, length(parameters)),
    target_parameters=randn(ComplexF64, length(parameters)),
    start_gamma=nothing, target_gamma=nothing)

This is a non-unicode variant where γ₁=start_parameters, γ₀=target_parameters, γ₁=start_gamma, γ₀=target_gamma.

HomotopyContinuation.CoefficientHomotopy — Type
CoefficientHomotopy(support, start_coeffs, target_coeffs)

Construct the homotopy $H(x, t) = ∑_{a ∈ Aᵢ} (c_a t + (1-t)d_a) x^a$ where $c_a$ are the start coefficients and $d_a$ the target coefficients.

We also provide more specialised homotopies, which are mostly used internally currently but could be useful in conjunction with the CoreTracker primitive.

HomotopyContinuation.PatchedHomotopy — Type
PatchedHomotopy(H::AbstractHomotopy, patch, v::PVector)

Augment the homotopy H with the given patch v. This results in the system [H(x,t); v ⋅ x - 1]

Interface for custom homotopies

The great thing is that you are not limited to the homotopies provided by default. You can define your own homotopy by defining a struct with super type AbstractHomotopy. For this the following interface has to be defined.

Types

Mandatory

The following methods are mandatory to implement.

HomotopyContinuation.cache — Method
cache(H::AbstractHomotopy, x, t)::AbstractHomotopyCache

Create a cache for the evaluation (incl. Jacobian) of F with elements of the type of x. The default implementation returns HomotopyNullCache.

HomotopyContinuation.evaluate! — Method
evaluate!(u, H::AbstractHomotopy, x, t, cache::AbstractHomotopyCache)

Evaluate the homotopy H at (x, t) and store the result in u.

HomotopyContinuation.jacobian! — Method
jacobian!(u, H::AbstractHomotopy, x, t, cache::AbstractHomotopyCache)

Evaluate the Jacobian of the homotopy H at (x, t) and store the result in u.

HomotopyContinuation.dt! — Function
dt!(u, H::AbstractHomotopy, x, t, cache::AbstractHomotopyCache)

Evaluate the homotopy H at (x, t) and store the result in u.

Base.size — Method
Base.size(H::AbstractHomotopy)

Returns a tuple (m, n) indicating that H is a homotopy of m polynomials m in n variables.

Optional

HomotopyContinuation.evaluate_and_jacobian! — Function
evaluate_and_jacobian!(u, U, F, x, t, cache::AbstractHomotopyCache)

Evaluate the homotopy H and its Jacobian at (x, t) and store the results in u (evalution) and U (Jacobian).

HomotopyContinuation.jacobian_and_dt! — Function
jacobian_and_dt!(U, u, H, x, t, cache::AbstractHomotopyCache)

Evaluate the homotopy H and its derivative w.r.t. t at (x, t) and store the results in u (evalution) and v (∂t).

HomotopyContinuation.jacobian_and_dt — Function
jacobian_and_dt(H::AbstractHomotopy, x, t, cache::AbstractHomotopyCache)

Evaluate the homotopy H and its derivative w.r.t. t at (x, t).

HomotopyContinuation.jacobian — Method
jacobian(H::AbstractHomotopy, x, t, cache::AbstractHomotopyCache)

Evaluate the Jacobian of the homotopy H at (x, t).

HomotopyContinuation.dt — Method
dt(H::AbstractHomotopy, x::AbstractVector, cache::AbstractHomotopyCache)

Evaluate the homotopy H at (x, t).

HomotopyContinuation.basehomotopy — Function
basehomotopy(H::AbstractHomotopy)

Returns the 'proper' homotopy describing the problem. Any wrapper homotopy recursively calls wrappedhomotopy with the wrapped homotopy as argument.