Data structures for polynomial systems

Polynomial systems can be represented in numerous ways in a computer and each representation has certain tradeoffs. For our purposes the most important thing is that it is fast to evaluate the system. Therefore we automatically convert an input given by DynamicPolynomials to another representation more suitable for numerically evaluations. The default is currently FPSystem.

Default systems

We provide the following systems by default.

HomotopyContinuation.FPSystem — Type.

FPSystem(polynomials, vars) <: AbstractSystem

Create a polynomial system using the FixedPolynomials package.

HomotopyContinuation.SPSystem — Type.

SPSystem(polynomials, vars) <: AbstractSystem

Create a system using the StaticPolynomials package. Note that StaticPolynomials leverages Julias metaprogramming capabilities to automatically generate functions to evaluate the system and its Jacobian. These generated functions are very fast but at the cost of possibly large compile times. The compile time depends on the size of the support of the polynomial system. If you intend to solve a large system or you need to solve a system with the same support but different coefficients even large compile times can be worthwile. As a general rule of thumb this usually is twice as fast as solving the same system using FPSystem.

Example

You can use SPSystem as follows with solve

@polyvar x y
F = [x^2+3y^4-2, 2y^2+3x*y+4]
solve(F, system=SPSystem)

HomotopyContinuation.FixedHomotopy — Type.

FixedHomotopy(H, t) <: AbstractSystem

Fix a homotopy H(x,t) at t

HomotopyContinuation.FixedParameterSystem — Type.

FixedParameterSystem(F, p) <: AbstractSystem

Fix a parameterized system F(x; p) at p, i.e., it is treated as a system without parameters.

HomotopyContinuation.CompositionSystem — Type.

CompositionSystem(composition::Composition, systems_constructor) <: AbstractSystem

A system representing the composition of polynomial maps.

Interface for custom systems

The great thing is that you are not limited to the systems provided by default. Maybe your polynomial system has a particular structure which you want to use to efficiently evaluate it. For this you can define your own homotopy by defining a struct with super type AbstractSystem. For this the following interface has to be defined.

Types

HomotopyContinuation.AbstractSystem — Type.

AbstractSystem

Representing a system of polynomials.

HomotopyContinuation.AbstractSystemCache — Type.

AbstractSystemCache

A cache to avoid allocations for the evaluation of an AbstractSystem.

HomotopyContinuation.SystemNullCache — Type.

SystemNullCache

An empty cache if no cache is necessary.

Mandatory

The following methods are mandatory to implement.

HomotopyContinuation.cache — Method.

cache(F::AbstractSystem, x)::AbstractSystemCache

Create a cache for the evaluation (incl. Jacobian) of F with elements of the type of x.

cache(F::AbstractSystem, x, p)::AbstractSystemCache

Create a cache for the evaluation (incl. Jacobian) of F with elements of the type of x and parameters p.

HomotopyContinuation.evaluate! — Method.

evaluate!(u, F::AbstractSystem, x, cache::AbstractSystemCache)

Evaluate the system F at x and store the result in u.

evaluate!(u, F::AbstractSystem, x, p, cache::AbstractSystemCache)

Evaluate the system F at x and parameters p and store the result in u.

HomotopyContinuation.evaluate — Function.

evaluate(F::AbstractSystem, x::AbstractVector, cache=cache(F, x))

Evaluate the system F at x.

evaluate(F::AbstractSystem, x::AbstractVector, p, cache=cache(F, x))

Evaluate the system F at x and parameters p.

HomotopyContinuation.jacobian! — Method.

jacobian!(u, F::AbstractSystem, x , cache::AbstractSystemCache)

Evaluate the Jacobian of the system F at x and store the result in u.

jacobian!(u, F::AbstractSystem, x , p, cache::AbstractSystemCache)

Evaluate the Jacobian of the system F at x and parameters p and store the result in u.

HomotopyContinuation.jacobian — Function.

jacobian(F::AbstractSystem, x, cache=cache(F, x))

Evaluate the Jacobian of the system F at x.

jacobian(F::AbstractSystem, x , p, cache::AbstractSystemCache)

Evaluate the Jacobian of the system F at x and parameters p.

Base.size — Method.

Base.size(F::AbstractSystem)

Returns a tuple (m, n) indicating that F is a system of m polynomials m in n variables.

Additionally if the system should support parameter homotopies it needs to support

HomotopyContinuation.differentiate_parameters! — Function.

differentiate_parameters!(u, F::AbstractSystem, x, p, cache::AbstractSystemCache)

Evaluate the Jacobian of the system F at x and parameters p w.r.t. the parameters and store the result in u.

HomotopyContinuation.differentiate_parameters — Function.

differentiate_parameters(F::AbstractSystem, x, p, cache=cache(F, x))

Evaluate the Jacobian of the system F at x and parameters p w.r.t. the parameters

Optional

The following methods are mandatory to implement. The following are optional to implement but usually you want to define at least cache.

HomotopyContinuation.evaluate_and_jacobian! — Method.

evaluate_and_jacobian!(u, U, F, x , cache::AbstractSystemCache)

Evaluate the system F and its Jacobian at x and store the results in u (evalution) and U (Jacobian).

HomotopyContinuation.evaluate_and_jacobian! — Method.

evaluate_and_jacobian!(u, U, F, x, p, cache::AbstractSystemCache)

Evaluate the system F and its Jacobian at x and parameters p and store the results in u (evalution) and U (Jacobian).