Homotopies

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.StraightLineHomotopy — Type.
StraightLineHomotopy(G, F; gamma=exp(i * 2π*rand()))

Construct the homotopy $H(x, t) = γtG(x) + (1-t)F(x)$.

HomotopyContinuation.FixedPointHomotopy — Type.
FixedPointHomotopy(F, x₀; gamma=exp(i * 2π*rand()))

Construct the homotopy $H(x, t) = (1-t)F(x) + γt(x-x₀)$.

HomotopyContinuation.ParameterHomotopy — Type.
ParameterHomotopy(F, parameters;
    variables=setdiff(MP.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(MP.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.

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

HomotopyContinuation.AbstractHomotopy — Type.
AbstractHomotopy

Representing a homotopy.

HomotopyContinuation.AbstractHomotopyCache — Type.
AbstractHomotopyCache

A cache to avoid allocations for the evaluation of an AbstractHomotopy.

HomotopyContinuation.HomotopyNullCache — Type.
HomotopyNullCache

The default AbstractHomotopyCache containing nothing.

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.evaluate_and_jacobian — Function.
evaluate_and_jacobian(H::AbstractHomotopy, x, t, cache::AbstractHomotopyCache)

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

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.evaluate — Method.
evaluate(H::AbstractHomotopy, x, t, cache::AbstractHomotopyCache)

Evaluate the homotopy H 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.