Reference

AffinePatches

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

HomotopyContinuation.OrthogonalPatchType.
OrthogonalPatch()

The orthogonal patch is a dynamically changing patch. It computes in such a way that ||x||=1 with respect to the 2-norm. See (for example) Section 3.2 in [HR18].

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

Deprecated

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:

HomotopyContinuation.EulerType.
Euler()

This uses the explicit Euler method for prediction, also known as the tangent predictor.

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
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!(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