Setting up homotopies

StraightLineHomotopy(start, target)

Construct the homotopy t * start + (1-t) * target.

start and target have to match and to be one of the following

• Vector{<:MP.AbstractPolynomial} where MP is MultivariatePolynomials

• MP.AbstractPolynomial

• Vector{<:FP.Polynomial} where FP is FixedPolynomials

StraightLineHomotopy{T}(start, target)

You can also force a specific coefficient type T.

GeodesicOnTheSphere(start, target)

Homotopy is the geodesic from g=start/|start| (t=1) to f=target/|target| (t=0):

H(x,t) = (cos(tα) - sin (tα)cos(α)/sin(α)) f + sin(tα) / sin(α) * g

where $α = cos |<f,g>|$. The constructor automatically homgenizes start and target.

start and target have to match and to be one of the following

• Vector{<:MP.AbstractPolynomial} where MP is MultivariatePolynomials

• MP.AbstractPolynomial

• Vector{<:FP.Polynomial} where FP is FixedPolynomials

GeodesicOnTheSphere{T}(start, target)

You can also force a specific coefficient type T.

totaldegree(H::Type{AbstractPolynomialHomotopy}, F, [unitroots=false])

Construct a total degree homotopy of type H with F and an iterator of its solutions. This is the homotopy with start system

and target system F, where $d_i$ is the degree of the $i$-th polynomial of F. If unitroots=true then $b_i=1$ otherwise $b_i$ is a random complex number (with real and imaginary part in the unit interval).

Example

H, startsolutions = totaldegree(StraightLineHomotopy{Complex128}, [x^2+y+1, x^3*y-2])

TotalDegreeSolutionIterator(degrees, b)

Given the Vectors degrees and b TotalDegreeSolutionIterator enumerates all solutions of the system

where $d_i$ is degrees[i] and $b_i$ is b[i].

totaldegree_startsystem(F::Vector{FP.Polynomial{<:Complex}}, [unit_roots=false])

Return the system

where $d_i$ is the degree of the $i$-th polynomial of F and an iterator of its solutions. If unitroots=true then $b_i=1$ otherwise $b_i$ is a random complex number (with real and imaginary part in the unit interval).

randomhomotopy(::Type{AbstractPolynomialHomotopy{T}}, size::Int; kwargs...)

Create a total degree homotopy where the target system is a randomsystem(T, size, size; kwargs...).

Example

julia> H, solutions = randomhomotopy(StraightLineHomotopy{Complex128}, 2, mindegree=3, maxdegree=6);
julia> length(H)
3
julia> nvariables(H)
3

randomsystem([T=Complex128,] nequations::Int, nvars::Int; mindegree=0, maxdegree=5, rng=Base.Random.GLOBAL_RNG, density=rand() * 0.8 + 0.1)

Creates a random polynomial system of nequations equations with nvars variables (named $x_1$, ...$x_{nvars}$). Each polynomial has a total degree uniformly drawn from $[mindegree, maxdegree]$. The coefficients are drawn independently from the given rng. With density you can control how many coefficients are non-zero. A value of 1.0 creates a dense polynomial (i.e. every coefficient is non-zero). A value of 0.5 creates a polynomial where only half of all monomials are non zero.

randomsystem([T=Complex128,] degrees::Vector{Int}, variables::Vector{Symbol}; rng=N(0,1))

Create a random polynomial system with the given degrees and variables.

evaluate(H::AbstractPolynomialHomotopy, x, t)

Evaluate the homotopy H at x to time t, i.e. $H(x,t)$.

evaluate(H::AbstractPolynomialHomotopy, x, t, cfg::PolynomialHomotopyConfig)

Evaluate the homotopy H at x to time t using the precompuated values in cfg. Note that this is significantly faster than evaluate(H, x, t).

evaluate!(u::Vector, H::AbstractPolynomialHomotopy, x, t)

Evaluate the homotopy H at x to time t, i.e. $H(x,t)$, and store the result in u.

evaluate!(u::AbstractVector, H::AbstractPolynomialHomotopy, x, t, cfg::PolynomialHomotopyConfig)

Evaluate the homotopy H at x to time t using the precompuated values in cfg and store the result in u.

jacobian(H::AbstractPolynomialHomotopy, x, t, cfg::PolynomialHomotopyConfig)

Compute the jacobian of H at x and t using the precomputed values in cfg. The jacobian is constructed w.r.t. x, i.e. it doesn't contain the partial derivatives w.r.t. t.

jacobian!(u, H::AbstractPolynomialHomotopy, x, t, cfg::PolynomialHomotopyConfig)

Compute the jacobian of H at x and t using the precomputed values in cfg and store the result in u.

jacobian!(r::JacobianDiffResult, H::AbstractPolynomialHomotopy, x, t, cfg::PolynomialHomotopyConfig)

Compute $H(x, t)$ and the jacobian of H at x and t at once using the precomputated values in cfg and store thre result in r. This is faster than computing both values separetely.

Example

cfg = PolynomialHomotopyConfig(H)
r = JacobianDiffResult(cfg)
jacobian!(r, H, x, t, cfg)

value(r) == H(x, t)
jacobian(r) == jacobian(H, x, t, cfg)

dt(H::AbstractPolynomialHomotopy, x, t, cfg::PolynomialHomotopyConfig)

Compute the derivative of H w.r.t. $t$ at x and t using the precomputed values in cfg.

dt!(u, H::AbstractPolynomialHomotopy, x, t, cfg::PolynomialHomotopyConfig)

Compute the derivative of H w.r.t. $t$ at x and t using the precomputed values in cfg and store the result in u.

dt!(r::DtDiffResult, H::AbstractPolynomialHomotopy, x, t, cfg::PolynomialHomotopyConfig)

Compute the derivative of H w.r.t. $t$ at x and t using the precomputed values in cfg and store the result in r. This is faster than computing both values separetely.

Example

cfg = PolynomialHomotopyConfig(H)
r = DtDiffResult(cfg)
dt!(r, H, x, t, cfg)

value(r) == H(x, t)
dt(r) == dt(H, x, t, cfg)

homogenize(H::AbstractPolynomialHomotopy)

Homogenize the homotopy H. This adds an additional variable. If H is already homogenized, this is the identity.

dehomogenize(H::AbstractPolynomialHomotopy)

Dehomogenize the homotopy H. This removes the first variable. If H is not homogenized, this is the identity.

ishomogenized(H::AbstractPolynomialHomotopy)

Check whether the homotopy H was homogenized.

ishomogenous(H::AbstractPolynomialHomotopy)

Check whether the homotopy H is homogenous. This does not imply that H was homogenized.

nvariables(H::AbstractPolynomialHomotopy)

The number of variables which H expects as input, i.e. to evaluate H(x,t) x has to be a vector of length nvariables(H).

weylnorm(H::AbstractPolynomialHomotopy)

Creates a function with variable t that computes the Weyl norm (or Bombieri norm) of $H(x,t)$. See here for details about the Weyl norm.

gammatrick!(H::AbstractPolynomialHomotopy{Complex} [, seed::Int]])

Scale the coefficients of the start system of H with a random complex number picked uniformly from the (complex) unit circle. Use this to make the paths $z(t)$ generic.

gammatrick!(H::AbstractPolynomialHomotopy{Complex}, γ::Complex)

You can also pass a scaling factor directly.

gammatrick(H::AbstractPolynomialHomotopy{Complex} , γ::Number)

Scale the coefficients of the start system of H with γ.

gammatrick(H::AbstractPolynomialHomotopy{Complex})

A a random complex number γ is picked uniformly from the (complex) unit circle and then scale the coefficients of the start system of H with γ. This returns the new H and γ.

κ(H, z, t, cfg)

Computes the condition number of H at (z, t) (with config cfg). See Condition^[1] for details

Proposition 16.10: κ(f,z) := ‖f‖ ‖ Df(z)^† diag(‖ z ‖^{d_i-1}) ‖

[1]: Condition, Bürgisser and Cucker

κ_norm(H, z, t, cfg)

Computes the condition number of H at (z, t) (with config cfg). See Condition^[1] for details

Eq. (16.11): κ_norm(f,z) := ‖f‖ ‖ Df(z)^† diag(√{d_i}‖ z ‖^{d_i-1}) ‖

[1]: Condition, Bürgisser and Cucker

μ_norm(H, z, t, cfg)

Computes the condition number of H at (z, t) (with config cfg). See Condition^[1] for details

Definition 16.43: μ_norm(f,z) := ‖f‖ ‖ (Df(z)-(T_z))^{-1} diag(√{d_i}‖ z ‖^{d_i-1}) ‖

[1]: Condition, Bürgisser and Cucker