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),
    startparameters=randn(ComplexF64, length(parameters)),
    targetparameters=randn(ComplexF64, length(parameters)),
    startgamma=nothing, targetgamma=nothing)

This is a non-unicode variant where γ₁=startparameters, γ₀=targetparameters, γ₁=startgamma, γ₀=targetgamma.

We also provide more specialised homotopies, which are mostly used internally currently but could be useful in conjunction with the PathTracker 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.