# Homotopies

A homotopy is a function

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

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

primitive.

`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]`

`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

`AbstractHomotopy`

Representing a homotopy.

`AbstractHomotopyCache`

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

.

`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

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

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

.

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