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.Homotopies.StraightLineHomotopy — Type.

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

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

HomotopyContinuation.Homotopies.FixedPointHomotopy — Type.

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

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

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

HomotopyContinuation.Homotopies.PatchedHomotopy — Type.

PatchedHomotopy(H::AbstractHomotopy, patch, v::AbstractProjectiveVector)

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

HomotopyContinuation.Homotopies.PatchSwitcherHomotopy — Type.

PatchSwitcherHomotopy(H::AbstractHomotopy, patch, v::AbstractProjectiveVector)

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 Homotopies.AbstractHomotopy. For this the following interface has to be defined.

Types

HomotopyContinuation.HomotopiesBase.AbstractHomotopy — Type.

AbstractHomotopy

Representing a homotopy.

HomotopyContinuation.HomotopiesBase.AbstractHomotopyCache — Type.

AbstractHomotopyCache

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

HomotopyContinuation.HomotopiesBase.NullCache — Type.

NullCache

The default AbstractHomotopyCache containing nothing.

Mandatory

The following methods are mandatory to implement.

HomotopyContinuation.HomotopiesBase.cache — Function.

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 HomotopiesBase.NullCache.

HomotopyContinuation.HomotopiesBase.evaluate! — Function.

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

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

HomotopyContinuation.HomotopiesBase.jacobian! — Function.

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.HomotopiesBase.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.HomotopiesBase.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.HomotopiesBase.evaluate_and_jacobian — Function.

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

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

HomotopyContinuation.HomotopiesBase.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.HomotopiesBase.evaluate — Function.

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

Evaluate the homotopy H at (x, t).

HomotopyContinuation.HomotopiesBase.jacobian — Function.

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

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

HomotopyContinuation.HomotopiesBase.dt — Function.

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

Evaluate the homotopy H at (x, t).

HomotopyContinuation.HomotopiesBase.precondition! — Function.

precondition!(H::AbstractHomotopy, x, t, cache)

Prepare a homotopy for things like pathtracking starting at x and t. This can modify x as well as H and anything in cache. By default this is a no-op. If H wraps another homotopy this should call precondition! on this as well.

HomotopyContinuation.HomotopiesBase.update! — Function.

update!(H::AbstractHomotopy, x, t, cache)

Update a homotopy for new values of x and x, i.e., update an affine patch. This can modify x as well as H and anything in cache. By default this is a no-op. If H wraps another homotopy this should call update! on this as well.

HomotopyContinuation.HomotopiesBase.basehomotopy — Function.

basehomotopy(H::AbstractHomotopy)

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