# Homotopies

Homotopies (`AbstractHomotopy`

) are at the heart of homotopy continuation. A homotopy is a parameterized family $H(x,t)$ of polynomial systems. By convention, homotopies are tracked from $t=1$ to $t=0$, i.e., $H(x,1)$ is considered the *start system* and $H(x,0)$ is the *target system*.

`HomotopyContinuation.ModelKit.AbstractHomotopy`

— Type`AbstractHomotopy`

An abstract type representing a homotopy $H(x, t)$ where $x$ are variables and $t$ is space / time.

As for `AbstractSystem`

s, `AbstractHomotopy`

and `Homotopy`

share different purposes. A `Homotopy`

is intended for formulating your problem symbolically. A `Homotopy`

can be converted to two different basic `AbstractHomotopy`

s, a `CompiledHomotopy`

(fast, but introduce compilation overhead) and an `InterpretedHomotopy`

(slower, but not compilation overhead).

`HomotopyContinuation.ModelKit.CompiledHomotopy`

— Type`CompiledHomotopy <: AbstractHomotopy`

An `AbstractHomotopy`

which automatically compiles a straight line program for the fast evaluation of a homotopy `H`

and its Jacobian. For large homotopies the compilation can take some time and require a large amount of memory. If this is a problem consider `InterpretedHomotopy`

.

`CompiledSystem(F::System; optimizations = true)`

Construct a `CompiledSystem`

from the given `System`

`F`

. If `optimizations = true`

then `optimize`

is called on `F`

before compiling.

`HomotopyContinuation.ModelKit.InterpretedHomotopy`

— Type`InterpretedHomotopy <: AbstractHomotopy`

An `AbstractHomotopy`

which automatically generates a program for the fast evaluation of `H`

and its Jacobian. The program is however, not compiled but rather interpreted. See also `CompiledHomotopy`

.

`InterpretedHomotopy(H::Homotopy; optimizations = true)`

Construct an `InterpretedHomotopy`

from the given `Homotopy`

`H`

. If `optimizations = true`

then `optimize`

is called on `H`

before compiling.

`HomotopyContinuation.MixedHomotopy`

— Type`MixedHomotopy`

A data structure which uses for `evaluate!`

and `evaluate_and_jacobian!`

a `CompiledHomotopy`

and for `taylor!`

an `InterpretedHomotopy`

.

`HomotopyContinuation.fixed`

— Method`fixed(H::Homotopy; compile::Union{Bool,Symbol} = mixed)`

Constructs either a `CompiledHomotopy`

(if `compile = :all`

), an `InterpretedHomotopy`

(if `compile = :none`

) or a `MixedHomotopy`

(`compile = :mixed`

).

Below you can find a list of all pre-defined homotopies. Additionally the following higher level constructors are exported.

`HomotopyContinuation.parameter_homotopy`

— Function`parameter_homotopy(F; start_parameters, target_parameters)`

Construct a `ParameterHomotopy`

. If `F`

is homogeneous, then a random affine chart is chosen (via `AffineChartHomotopy`

).

`HomotopyContinuation.linear_subspace_homotopy`

— Function`linear_subspace_homotopy(F, V::LinearSubspace, W::LinearSubspace, intrinsic = nothing)`

Constructs an `IntrinsicSubspaceHomotopy`

(if `dim(V) < codim(V)`

or `intrinsic = true`

) or `ExtrinsicSubspaceHomotopy`

. Compared to the direct constructor, this also takes care of homogeneous systems.

## AffineChartHomotopy

`HomotopyContinuation.AffineChartHomotopy`

— Type`AffineChartHomotopy(H::AbstractHomotopy, v::PVector{T,N})`

Given a homotopy $H(x,t): (ℙ^{m_1} × ⋯ × ℙ^{m_N}) × ℂ → ℂⁿ$ this creates a new affine homotopy $H̄$ which operates on the affine chart defined by the vector $v ∈ ℙ^{m_1} × ⋯ × ℙ^{m_N}$ and the augmented conditions $vᵀx = 1$.

`HomotopyContinuation.on_affine_chart`

— Method`on_affine_chart(H::Union{Homotopy,AbstractHomotopy}, proj_dims)`

Construct an `AffineChartHomotopy`

on a randomly generated chart `v`

. Each entry is drawn idepdently from a univariate normal distribution.

## CoefficientHomotopy

`HomotopyContinuation.CoefficientHomotopy`

— Type```
CoefficientHomotopy(
F::Union{AbstractSystem,System};
start_coefficients,
target_coefficients,
)
```

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.

## FixedParameterHomotopy

`HomotopyContinuation.FixedParameterHomotopy`

— Type`FixedParameterHomotopy(H:AbstractHomotopy, parameters)`

Construct a homotopy from the given `AbstractHomotopy`

`H`

with the given `parameters`

fixed.

`HomotopyContinuation.fix_parameters`

— Method`fix_parameters(H::Union{Homotopy,AbstractHomotopy}, p; compile::Union{Bool,Symbol} = mixed)`

Fix the parameters of the given homotopy `H`

. Returns a `FixedParameterHomotopy`

.

## ExtrinsicSubspaceHomotopy

`HomotopyContinuation.ExtrinsicSubspaceHomotopy`

— Type`ExtrinsicSubspaceHomotopy`

## IntrinsicSubspaceHomotopy

`HomotopyContinuation.IntrinsicSubspaceHomotopy`

— Type```
IntrinsicSubspaceHomotopy(F::System, V::LinearSubspace, W::LinearSubspace)
IntrinsicSubspaceHomotopy(F::AbstractSystem, V::LinearSubspace, W::LinearSubspace)
```

Creates a homotopy $H(x,t) = F(γ(t)x)$ where $γ(t)$ is a family of affine subspaces such that $γ(1) = V$ and $γ(0) = W$. Here $γ(t)$ is the geodesic between `V`

and `W`

in the affine Grassmanian, i.e., it is the curve of minimal length connecting `V`

and `W`

. See also `LinearSubspace`

and `geodesic`

and the references therein.

`HomotopyContinuation.set_subspaces!`

— Function`set_subspaces!(H::IntrinsicSubspaceHomotopy, start::LinearSubspace, target::LinearSubspace)`

Update the homotopy `H`

to track from the affine subspace `start`

to `target`

.

## ParameterHomotopy

`HomotopyContinuation.ParameterHomotopy`

— Type```
ParameterHomotopy(F::Union{AbstractSystem,System}; start_parameters, target_parameters)
ParameterHomotopy(F::Union{AbstractSystem,System}, start_parameters, target_parameters)
```

Construct the parameter homotopy $H(x,t) = F(x; t p + (1 - t) q)$ where $p$ is `start_parameters`

and $q$ is `target_parameters`

.

## StraightLineHomotopy

`HomotopyContinuation.StraightLineHomotopy`

— Type```
StraightLineHomotopy(G::System, F::System; gamma = 1.0)
StraightLineHomotopy(G::AbstractSystem, F::AbstractSystem; gamma = 1.0)
```

Constructs the straight line homotopy $H(x, t) = γ t G(x) + (1-t) F(x)$ where $γ$ is `gamma`

.