# Reference

## AffinePatches

Affine patches are there to augment projective system such that they can be considered as (locally) affine system.

HomotopyContinuation.RandomPatchType
RandomPatch()

A random patch. For this we first draw entries of a vector v independently from a complex normal distribution (randn(ComplexF64)). And then normalize v with respect to the 2-norm.

## Input

We support any polynomials which follow the MultivariatePolynomials interface. By default we export the routines @polyvar, differentiate and variables from the DynamicPolynomials implementation. With these you can simply create variables

# Create variables x, y, z
@polyvar x y z
f = x^2+y^2+z^2

# You can also create an array of variables
@polyvar x[1:3] # This creates x1, x2, x3 accessed by x[1], x[2], x[3]
f = dot(x, x) # = x[1]^2+x[2]^2+x[3]^2

# Also you can create matrices of variables
# This creates x1_1, x1_2, x2_1, x2_2 accessed by
# x[1,1], x[1,2], x[2,1], x[2,2]
@polyvar x[1:2, 1:2]

We also provide methods construct compositions of polynomial systems:

HomotopyContinuation.composeFunction
compose(g, f)::Composition

Compose the polynomial systems g and f. You can also use the infix operator ∘ (written by \circ).

julia> @polyvar a b c x y z;
julia> g = [a * b * c];
julia> f = [x+y, y + z, x + z];
julia> expand(compose(g, f))
1-element Array{DynamicPolynomials.Polynomial{true,Int64},1}:
x²y + x²z + xy² + 2xyz + xz² + y²z + yz²

## Distances and norms

We provide functions for computing norms and distance. These are subtypes of AbstractNorm:

HomotopyContinuation.AbstractNormType
AbstractNorm

An AbstractNorm represents any norm of a vector space. All norms are callable. norm(x) computes the norm of x and norm(x,y) computes the distance norm(x - y).

They implement

LinearAlgebra.normMethod
norm(u, norm::AbstractNorm)

Compute the norm ||u|| with respect to the given norm norm.

The following norms are implemented:

HomotopyContinuation.WeightedNormType
WeightedNorm(d::AbstractVector, norm::AbstractNorm; options...)
WeightedNorm(norm::AbstractNorm, n::Integer; options...)
WeightedNorm(norm::AbstractNorm, x::AbstractVector; options...)

A WeightedNorm represents a weighted variant of norm norm of a n-dimensional vector space.A norm||x||is weighted by introducing a vector of additional weightsdsuch that the new norm is||D⁻¹x||whereDis the diagonal matrix with diagonald. The WeightedNorm is desigened to change the weights dynamically by using init!(::WeightedNorm, x) and update!(::WeightedNorm, x). The weights are there constructed such that $||D⁻¹x|| ≈ 1.0$. The weights can be accessed and changed by indexing.

Options

• scale_min = 0.001: The minimal size of dᵢ is scale_min time the (weighted) norm of x.
• scale_abs_min = min(scale_min^2, 200 * sqrt(eps())): The absolute minimal size of dᵢ.
• scale_max = 1.0 / eps() / sqrt(2): The absolute maximal size of dᵢ
HomotopyContinuation.update!Method
update!(w::WeightedNorm, x::AbstractVector)

Update the weighted norm w for x, this will interpolate between the previous weights and the norm of x.

## Path informations

HomotopyContinuation.path_infoFunction
path_info(tracker::CoreTracker, x, t₁ = 1.0, t₀ = 0.0)
path_info(tracker::PathTracker, x)

Track a path using the given tracker and start value x. This returns a struct containing detailed informations about the tracked path.

Example

julia> @polyvar x y;
julia> f = [x^2 + y^2 + 1, x + y - 3];
julia> tracker, starts = coretracker_startsolutions(f);
julia> path_info(tracker, first(starts))
CTPathInfo:
• # return code → success
• # steps (✓/✗) → 11 ( 10 / 1 )
• # factorizations → 31
• # ldivs → 66
┌───┬───────┬────────┬───────┬─────────┬─────────┬──────┬─────────┬───────────┬──────┬─────────┐
│   │     s │     Δs │     ω │   |Δx₀| │     acc │    κ │       ψ │ limit_acc │  |x| │     |r| │
├───┼───────┼────────┼───────┼─────────┼─────────┼──────┼─────────┼───────────┼──────┼─────────┤
│ ✓ │     0 │  0.117 │     1 │       0 │ 3.4e-17 │  1.5 │ 2.2e-17 │   3.4e-17 │    1 │ 6.7e-17 │
│ ✓ │ 0.117 │  0.117 │ 0.866 │ 0.00063 │ 2.7e-17 │ 2.31 │ 1.7e-17 │   2.7e-17 │ 1.13 │ 5.6e-17 │
│ ✓ │ 0.235 │    0.2 │ 0.817 │ 0.00086 │ 3.7e-14 │ 2.31 │ 1.7e-17 │   2.7e-17 │ 1.29 │ 5.6e-17 │
│ ✗ │ 0.435 │  0.166 │ 0.437 │   0.021 │ 3.4e-09 │ 2.31 │ 1.7e-17 │   2.7e-17 │ 1.53 │ 5.6e-17 │
│ ✓ │ 0.435 │  0.105 │  1.08 │   0.041 │ 3.4e-09 │ 2.31 │ 1.7e-17 │   2.7e-17 │ 1.53 │ 5.6e-17 │
│ ✓ │ 0.539 │  0.105 │  1.08 │  0.0053 │   1e-15 │ 7.03 │ 6.7e-16 │     1e-15 │ 1.47 │ 2.2e-15 │
│ ✓ │ 0.644 │ 0.0704 │ 0.652 │   0.039 │ 3.4e-08 │ 7.03 │ 6.7e-16 │     1e-15 │ 1.24 │ 2.2e-15 │
│ ✓ │ 0.714 │ 0.0816 │ 0.408 │  0.0057 │ 1.7e-12 │ 7.03 │ 6.7e-16 │     1e-15 │ 1.33 │ 2.2e-15 │
│ ✓ │ 0.796 │ 0.0999 │ 0.357 │  0.0049 │ 3.3e-12 │ 7.03 │ 6.7e-16 │     1e-15 │ 1.59 │ 2.2e-15 │
│ ✓ │ 0.896 │  0.104 │ 0.683 │  0.0032 │ 4.1e-12 │ 7.03 │ 6.7e-16 │     1e-15 │ 1.94 │ 2.2e-15 │
│ ✓ │     1 │      0 │ 0.748 │ 0.00082 │ 1.5e-16 │ 3.86 │ 6.8e-17 │   1.5e-16 │ 2.24 │ 1.3e-15 │
└───┴───────┴────────┴───────┴─────────┴─────────┴──────┴─────────┴───────────┴──────┴─────────┘

julia> tracker = pathtracker(f);

julia> path_info(tracker, first(starts))
PTPathInfo:
• # return code → success
• # steps (✓/✗) → 19 ( 18 / 1 )
• # factorizations → 56
• # ldivs → 114
┌───┬───────┬───────┬─────────┬──────────┬──────────┬──────┬───────────┬─────────┬───────┬─────────┬──────┐
│   │     s │    Δs │    |ν̇| │    min_ν │    max_ν │    κ │ limit_acc │     acc │     ω │   |Δx₀| │  |x| │
├───┼───────┼───────┼─────────┼──────────┼──────────┼──────┼───────────┼─────────┼───────┼─────────┼──────┤
│ ✓ │     0 │ 0.126 │     NaN │      NaN │      NaN │  1.5 │   9.6e-18 │ 9.6e-18 │     1 │       0 │    1 │
│ ✓ │ 0.126 │ 0.126 │     NaN │      NaN │      NaN │  1.5 │   5.4e-17 │ 5.4e-17 │ 0.874 │ 0.00098 │ 1.13 │
│ ✓ │ 0.251 │ 0.209 │     NaN │      NaN │      NaN │  1.5 │   5.4e-17 │ 5.6e-14 │ 0.829 │ 0.00094 │ 1.29 │
│ ✓ │  0.46 │ 0.234 │     NaN │      NaN │      NaN │  1.5 │   5.4e-17 │   3e-11 │ 0.733 │  0.0049 │ 1.51 │
│ ✓ │ 0.694 │  0.23 │     NaN │      NaN │      NaN │  1.5 │   5.4e-17 │ 2.6e-10 │ 0.767 │   0.008 │ 1.54 │
│ ✓ │ 0.924 │ 0.158 │     NaN │      NaN │      NaN │  1.5 │   5.4e-17 │   6e-08 │  1.16 │   0.028 │ 1.31 │
│ ✓ │  1.08 │ 0.154 │     NaN │      NaN │      NaN │  1.5 │   5.4e-17 │ 6.3e-11 │ 0.598 │  0.0093 │ 1.21 │
│ ✓ │  1.24 │  0.25 │     NaN │      NaN │      NaN │  1.5 │   5.4e-17 │ 8.9e-15 │ 0.395 │  0.0015 │  1.3 │
│ ✓ │  1.48 │  0.38 │     NaN │      NaN │      NaN │  1.5 │   5.4e-17 │ 8.7e-14 │ 0.293 │  0.0022 │ 1.51 │
│ ✗ │  1.87 │ 0.135 │     NaN │      NaN │      NaN │  1.5 │   5.4e-17 │   8e-13 │ 0.686 │  0.0022 │ 1.78 │
│ ✓ │     2 │ 0.314 │    0.39 │    -0.26 │    -0.26 │  1.5 │   5.8e-17 │ 5.8e-17 │ 0.566 │ 8.8e-06 │ 1.85 │
│ ✓ │  2.31 │ 0.314 │    0.23 │    -0.17 │    -0.16 │ 3.64 │   1.2e-16 │ 1.2e-16 │ 0.491 │  0.0001 │ 1.97 │
│ ✓ │  2.63 │  1.24 │    0.15 │    -0.11 │     -0.1 │ 3.64 │   1.2e-16 │ 3.7e-10 │  0.84 │   3e-05 │ 2.05 │
│ ✓ │  3.86 │  1.71 │   0.028 │   -0.025 │   -0.023 │ 3.64 │   1.2e-16 │ 1.4e-12 │ 0.751 │   0.002 │ 2.19 │
│ ✓ │  5.58 │  2.84 │  0.0043 │  -0.0042 │  -0.0037 │ 3.71 │   7.9e-17 │ 7.9e-17 │ 0.275 │  0.0017 │ 2.23 │
│ ✓ │  8.41 │  5.13 │ 0.00024 │ -0.00024 │ -0.00021 │ 3.71 │   7.9e-17 │ 2.3e-14 │ 0.244 │  0.0012 │ 2.24 │
│ ✓ │  13.5 │  13.3 │ 1.4e-06 │ -1.4e-06 │ -1.3e-06 │ 3.71 │   7.9e-17 │ 1.1e-08 │ 0.245 │  0.0003 │ 2.24 │
│ ✓ │  26.8 │    55 │ 4.3e-10 │ -2.5e-12 │ -2.2e-12 │ 3.67 │   1.7e-16 │ 1.7e-16 │ 0.275 │ 9.8e-06 │ 2.24 │
│ ✓ │  81.8 │     0 │ 4.3e-10 │ -2.5e-12 │ -2.2e-12 │ 3.67 │   1.2e-16 │ 1.2e-16 │ 0.275 │ 1.8e-09 │ 2.24 │
└───┴───────┴───────┴─────────┴──────────┴──────────┴──────┴───────────┴─────────┴───────┴─────────┴──────┘

## Polynomial Utilities

HomotopyContinuation.homogenizeFunction
homogenize(f::MP.AbstractPolynomial, variable=uniquevar(f))

Homogenize the polynomial f by using the given variable variable.

homogenize(F::Vector{<:MP.AbstractPolynomial}, variable=uniquevar(F))

Homogenize each polynomial in F by using the given variable variable.

homogenize(f::MP.AbstractPolynomial, v::Vector{<:MP.AbstractVariable}, variable=uniquevar(f))

Homogenize the variables v in the polynomial f by using the given variable variable.

homogenize(F::Vector{<:MP.AbstractPolynomial}, v::Vector{<:MP.AbstractVariable}, variable=uniquevar(F))

Homogenize the variables v in each polynomial in F by using the given variable variable.

HomotopyContinuation.is_homogeneousFunction
is_homogeneous(f::MP.AbstractPolynomialLike)

Checks whether f is homogeneous.

is_homogeneous(f::MP.AbstractPolynomialLike, vars)

Checks whether f is homogeneous in the variables vars with possible weights.

is_homogeneous(F::Vector{MP.AbstractPolynomialLike}, variables)

Checks whether each polynomial in F is homogeneous in the variables variables.

HomotopyContinuation.linear_systemFunction
linear_system(f::Vector{<:MP.AbstractPolynomialLike})

Given a polynomial system which represents a linear system $Ax=b$ return A and b. If f is not a linear system nothing is returned.

Example

julia> @polyvar x y z;
julia> f = [2x+3y+z+5, -1x+2y+4z-2];
julia> A, b = linear_system(f);
julia> A
2×3 Array{Int64,2}:
2  3  1
-1  2  4

julia> b
2-element Array{Int64,1}:
-5
2

## Predictors and Correctors

We use a predictor-corrector scheme to track paths. While we have a fixed implementation of Newton's method as a corrector there multiple predictors available:

## Projective vectors

To represent solutions in projective spaces we use the ProjectiveVectors.jl package. The following methods are re-exported from the package.

ProjectiveVectors.PVectorType
PVector{T, N} <: AbstractProjectiveVector{T, N}

A PVector represents a projective vector z which lives in a product of N projective spaces $P(T)^{dᵢ}$. The underlying data structure is a Vector{T}.

PVector(v::AbstractVector, dims::NTuple{N,Int}) where N

Create a projective vector v living in a product of projective spaces with (projective) dimensions dims.

PVector(v, w, ...)

Create the product of projective vectors.

Example

julia> PVector([1,2,3], [4, 5])
[1 : 2 : 3] × [4 : 5]

julia> PVector([1, 2, 3, 4, 5], (2, 1))
[1 : 2 : 3] × [4 : 5]

julia> PVector([1,2,3], [4, 5], [6, 7, 8])
[1 : 2 : 3] × [4 : 5] × [6 : 7 : 8]
ProjectiveVectors.dimension_indicesFunction
dimension_indices(z::PVector{T, N})
dimension_indices(dims::NTuple{N, Int})

Return a tuple of N UnitRanges indexing the underlying data.

Example

julia> v = PVector([4, 5, 6], [2, 3], [1, 2])
PVector{Int64, 3}:
[4, 5, 6] × [2, 3] × [1, 2]

julia> dimension_indices(v)
(1:3, 4:5, 6:7)
ProjectiveVectors.affine_chartFunction
affine_chart(z::PVector)

Return the affine chart corresponding to the projective vector. This can be seen as the inverse of embed.

Example

julia> v = embed([2.0, 3, 4, 5, 6, 7], (2, 3, 1))
PVector{Float64, 3}:
[2.0, 3.0, 1.0] × [4.0, 5.0, 6.0, 1.0] × [7.0, 1.0]

julia> affine_chart(v)
6-element Array{Float64,1}:
2.0
3.0
4.0
5.0
6.0
7.0
ProjectiveVectors.embedFunction
embed(xs::AbstractVector...; normalize=false)
embed(x::AbstractVector{T}, dims::NTuple{N, Int}; normalize=false)::PVector{T, N}

Embed an affine vector x in a product of affine spaces by the map πᵢ: xᵢ -> [xᵢ; 1] for each subset xᵢ of x according to dims. If normalize is true the vector is normalized.

Examples

julia> embed([2, 3])
PVector{Int64, 1}:
[2, 3, 1]

julia> embed([2, 3], [4, 5, 6])
PVector{Int64, 2}:
[2, 3, 1] × [4, 5, 6, 1]

julia> embed([2.0, 3, 4, 5, 6, 7], (2, 3, 1))
PVector{Float64, 3}:
[2.0, 3.0, 1.0] × [4.0, 5.0, 6.0, 1.0] × [7.0, 1.0]

julia> embed([2.0, 3, 4, 5, 6, 7], (2, 3, 1), normalize=true)
PVector{Float64, 3}:
[0.5345224838248488, 0.8017837257372732, 0.2672612419124244] × [0.45291081365783825, 0.5661385170722978, 0.6793662204867574, 0.11322770341445956] × [0.9899494936611666, 0.1414213562373095]
LinearAlgebra.:×Function
×(v::PVector, w::PVector...)

Operator version of combine.

Example

julia> v = PVector([1, 2, 3]);
julia> w = PVector([4, 5]);
julia> v × w
[1 : 2 : 3] × [4 : 5]
ProjectiveVectors.componentFunction
component(v::PVector{T,N}, i)::PVector{T,1}

Obtain the i-th component of $v ∈ P(ℂ^n₁) × ... × P(ℂ^nⱼ)$.

Example

julia> v = PVector([1, 2, 3]);
julia> w = PVector([4, 5]);
julia> v × w
[1 : 2 : 3] × [4 : 5]
julia> component(v × w, 1)
[1 : 2 : 3]
# alternative you can also indexing
julia> (v × w)[1,:]
[1 : 2 : 3]
ProjectiveVectors.componentsFunction
components(v::PVector{T,N})::NTuple{N, PVector{T, 1}}

Decompose the element $v ∈ P(ℂ^n₁) × ... × P(ℂ^nⱼ)$ into $(v₁, …, vⱼ) = v$

Example

julia> v = PVector([1, 2, 3]);
julia> w = PVector([4, 5]);
julia> v × w
[1 : 2 : 3] × [4 : 5]
julia> components(v × w) == (v, w)
true
ProjectiveVectors.combineFunction
combine(v::PVector, w::PVector...)

Combine the projective vectors v and wᵢ to the flattened product. There is also an operator version, × (written imes<tab>).

Example

julia> v = PVector([1, 2, 3]);
julia> w = PVector([4, 5]);
julia> combine(v, w)
[1 : 2 : 3] × [4 : 5]

## Unique points and multiplicities

We provide functions for sorting analyzing arrays of vectors.

### Unique points

We provide the unique_points methods to sort through solutions.

HomotopyContinuation.unique_pointsFunction
unique_points(points::AbstractVector{<:AbstractVector}; options...)

Compute all unique points with respect to the given options. See UniquePoints for possible options. In particular, it is possible to pass group actions.

Example

julia> pts = [[1.0,0.5], [1.0,0.5], [0.5,1.0]];
julia> unique_points(pts)
2-element Array{Array{Float64,1},1}:
[1.0, 0.5]
[0.5, 1.0]

julia> unique_points(pts; group_action = x -> [x[2],x[1]])
1-element Array{Array{Float64,1},1}:
[1.0, 0.5]

The unique_points method is powered by the UniquePoints data structure.

HomotopyContinuation.UniquePointsType
UniquePoints{V<:AbstractVector, T, F<:Function}

A data structure which holds points of type V where T=real(eltype(V)). This data structure provides an efficient (poly)logarithmic check whether a point already exists where two points u,v are considered equal if F(u,v)<tol, where tol is a tolerance provided through the add! function.

UniquePoints(v::AbstractVector{<:Number}, distance::F)

Initialize the data structure with just one data point v.

UniquePoints(V::Vector{<:AbstractVector{<:Number}}, distance::F; tol=1e-5)

Initialize the data structure with all points in v. These are added in order by add! with the given tolerance tol. In particular, 'UniquePoints' structure will contain only points for which the pairwise distance given by F is less than tol.

UniquePoints(v; kwargs...) = UniquePoints(v, euclidean_distance; kwargs...)

If F is not specialized, euclidean_distance is used.

Optional keywords:

• check_real=true adds real from points from group orbits (if they exist). The default is check_real=true.
• The user can use group_action=foo or, if there is more than one group acting, group_actions=[foo, bar]. Then, points that are in the same group orbit are considered equal. See GroupActions for details regarding the application rules.

Examples

julia> points(UniquePoints([[1.0,0.5], [1.0,0.5], [0.5,1.0]]))
2-element Array{Array{Float64,1},1}:
[1.0, 0.5]
[0.5, 1.0]

julia> points(UniquePoints([[1.0,0.5], [1.0,0.5], [0.5,1.0]], group_action = x -> [x[2],x[1]]))
1-element Array{Array{Float64,1},1}:
[1.0, 0.5]

We provide several helper functions for UniquePoints.

HomotopyContinuation.is_containedFunction
is_contained(data::UniquePoints{V}, x::V; tol=1e-5)::Bool

Check whether x is contained in the data by using the tolerance tol to decide for duplicates.

is_contained(data::UniquePoints{V}, x::V, Val{true}(); tol=1e-5)::Int

If x is contained in data by using the tolerance tol return the index of the data point which already exists. If the data point is not existing -1 is returned. If data has the option check_real enabled, a -2 will be returned once a real vector was added.

HomotopyContinuation.add!Function
add!(data::UniquePoints{V}, x::V; tol=1e-5)::Bool

Add x to data if it doesn't already exists by using the tolerance tol to decide for duplicates.

add!(data::UniquePoints{V}, x::V, Val(true); tol=1e-5)::Int

If x is contained in data by using the tolerance tol to decide for duplicates return the index of the data point which already exists. If the data point is not existing add it to data and return -1. If data has the option check_real enabled, a -2 will be returned once a real vector was added. The element will be the last element of points(data).

HomotopyContinuation.simple_add!Function
simple_add!(data::UniquePoints{V}, x::V, tol::Real)::Bool

Similarly to add! but does not apply any group actions. If the data point is not existing add it to data and return -1. Otherwise the index of x in data.points is returned.

Base.empty!Function
empty!(collection) -> collection

Remove all elements from a collection.

Examples

julia> A = Dict("a" => 1, "b" => 2)
Dict{String,Int64} with 2 entries:
"b" => 2
"a" => 1

julia> empty!(A);

julia> A
Dict{String,Int64} with 0 entries
source
empty!(q::Deque{T})

Reset the deque.

empty!(collection) -> collection

Remove all elements from a collection.

Examples

julia> A = RobinDict("a" => 1, "b" => 2)
RobinDict{String,Int64} with 2 entries:
"b" => 2
"a" => 1

julia> empty!(A);

julia> A
RobinDict{String,Int64} with 0 entries
empty!(cb::CircularBuffer)

Reset the buffer.

empty!(data::UniquePoints)

Remove all points from data.

### Multiplicities

If instead of unique points, the user wants to have the information which points in an array of points appear with multiplicity, they should use the next function.

HomotopyContinuation.multiplicitiesFunction
multiplicities(vectors; distance=euclidean_distance, tol::Real = 1e-5, kwargs...)

Returns an array of arrays of integers. Each vector w in 'v' contains all indices i,j such that w[i] and w[j] have distance at most tol.

Optional keywords:

• check_real=true adds real from points from group orbits (if they exist) to the UniquePoints data structure used internally. The default is check_real=false.
• The user can use group_action=foo or, if there is more than one group acting, group_actions=[foo, bar]. Then, points that are in the same group orbit are considered equal. See GroupActions for details regarding the application rules.
julia> multiplicities([[1,0.5]; [1,0.5]; [1,1]])
[[1,2]]

This is the same as

multiplicities([[1,0.5]; [1,0.5]; [1,1]]; distance=(x,y) -> LinearAlgebra.norm(x-y))

Here is an example for using group actions.

julia> X = [[1, 2, 3, 4], [2,1,3,4], [1,2,4,3], [2,1,4,3]]
julia> permutation(x) = [x[2], x[1], x[3], x[4]]
julia> m = multiplicities(X, group_action = permutation)
[[1,2], [3,4]]
multiplicities(V::Results; tol=1e-6)

Returns a Vector of Vector{PathResult}s grouping the PathResults whose solutions appear with multiplicities greater 1 in 'V'. Two solutions are regarded as equal, when their pairwise distance is less than 'tol'.

The multiplicities functions may also be applied to Result; see here: multiplicities(::HomotopyContinuation.Results).

• HR18https://arxiv.org/pdf/1710.06362.pdf