Reference

AbstractAffinePatch

An affine patch is a hyperplane defined by $v⋅x-1=0$. The currently implemented affine patches are:

• EmbeddingPatch
• FixedPatch
• OrthogonalPatch
• RandomPatch

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

EmbeddingPatch()

Holds an PVector onto its affine patch. With this the effect is basically the same as tracking in affine space.

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.

FixedPatch()

The FixedPatch is similar to the OrthogonalPatch but it doesn't change during the tracking. Instead it only updates at the start of the tracking.

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²

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

distance(u, v, norm::AbstractNorm)

Compute the distance ||u-v|| with respect to the given norm norm.

norm(u, norm::AbstractNorm)

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

EuclideanNorm

The usual Euclidean norm resp. 2-norm.

InfNorm <: AbstractNorm

The infinity or maximum norm.

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ᵢ

weights(WN::WeightedNorm)

Returns the weights of the weighted norm.

init!(w::WeightedNorm, x::AbstractVector)

Setup the weighted norm w for x.

update!(w::WeightedNorm, x::AbstractVector)

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

euclidean_distance(u, v)

Compute ||u-v||₂.

euclidean_norm(u)

Compute ||u||₂.

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 │
└───┴───────┴───────┴─────────┴──────────┴──────────┴──────┴───────────┴─────────┴───────┴─────────┴──────┘

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.

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.

uniquevar(f::MP.AbstractPolynomialLike, tag=:x0)
uniquevar(F::MPPolys, tag=:x0)

Creates a unique variable.

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

Euler()

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

Heun()

The Heun predictor of order 2.

Ralston()

The Ralston predictor of order 2.

RK3()

The classical Runge-Kutta predictor of order 3.

RK4()

The classical Runge-Kutta predictor of order 4.

Pade21()

This uses a Padé-approximation of type (2,1) for prediction.

NullPredictor()

A predictor which does no prediction step, i.e., it just returns the input as its prediction.

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]

dims(z::PVector)

Dimensions of the projective spaces in which z lives.

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)

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

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]

×(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]

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]

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

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

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]

points(data::UniquePoints)

Return the points stored in data.

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.

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

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.

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

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(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'.