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

StraightLineHomotopy(G, F; gamma=exp(i * 2π*rand()))

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

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

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

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.

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.

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

AbstractHomotopy

Representing a homotopy.

AbstractHomotopyCache

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

HomotopyNullCache

The default AbstractHomotopyCache containing nothing.

Mandatory

The following methods are mandatory to implement.

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.

evaluate!(u, H::AbstractHomotopy, x, t, cache::AbstractHomotopyCache)

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

jacobian!(u, H::AbstractHomotopy, x, t, cache::AbstractHomotopyCache)

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

dt!(u, H::AbstractHomotopy, x, t, cache::AbstractHomotopyCache)

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

Base.sizeMethod.
Base.size(H::AbstractHomotopy)

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

Optional

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).

evaluate_and_jacobian(H::AbstractHomotopy, x, t, cache::AbstractHomotopyCache)

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

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).

jacobian_and_dt(H::AbstractHomotopy, x, t, cache::AbstractHomotopyCache)

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

evaluate(H::AbstractHomotopy, x, t, cache::AbstractHomotopyCache)

Evaluate the homotopy H at (x, t).

jacobian(H::AbstractHomotopy, x, t, cache::AbstractHomotopyCache)

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

dt(H::AbstractHomotopy, x::AbstractVector, cache::AbstractHomotopyCache)

Evaluate the homotopy H at (x, t).

basehomotopy(H::AbstractHomotopy)

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