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.Systems.FPSystem — Type.

FPSystem(polynomials, vars) <: AbstractSystem

Create a polynomial system using the FixedPolynomials package.

source

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

source

HomotopyContinuation.Systems.FixedHomotopy — Type.

FixedHomotopy(H, t) <: AbstractSystem

Fix a homotopy H(x,t) at t

source

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 Systems.AbstractSystem. For this the following interface has to be defined.

Types

HomotopyContinuation.SystemsBase.AbstractSystem — Type.

AbstractSystem

Representing a system of polynomials.

source

HomotopyContinuation.SystemsBase.AbstractSystemCache — Type.

AbstractSystemCache

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

source

HomotopyContinuation.SystemsBase.NullCache — Type.

NullCache

An empty cache if no cache is necessary.

source

Mandatory

The following methods are mandatory to implement.

HomotopyContinuation.SystemsBase.cache — Function.

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

Create a cache for the evaluation (incl. Jacobian) of F with elements of the type of x. The default implementation returns a NullCache.

source

HomotopyContinuation.SystemsBase.evaluate! — Function.

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

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

source

HomotopyContinuation.SystemsBase.evaluate — Function.

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

Evaluate the system F at x.

source

HomotopyContinuation.SystemsBase.jacobian! — Function.

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

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

source

HomotopyContinuation.SystemsBase.jacobian — Function.

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

Evaluate the Jacobian of the system F at x.

source

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.

source

Optional

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

HomotopyContinuation.SystemsBase.evaluate_and_jacobian! — Function.

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

source

HomotopyContinuation.SystemsBase.evaluate_and_jacobian — Function.

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

Evaluate the system F and its Jacobian at x.

source