# 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 `DynamicPolynomial`

s 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)
```

`FixedHomotopy(H, t) <: AbstractSystem`

Fix a homotopy `H(x,t)`

at `t`

`FixedParameterSystem(F, p) <: AbstractSystem`

Fix a parameterized system `F(x; p)`

at `p`

, i.e., it is treated as a system without parameters.

`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

`AbstractSystem`

Representing a system of polynomials.

`AbstractSystemCache`

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

.

`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=cache(F, x))`

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

If a total degree homotopy with a system as input should be supported `degrees(F)`

needs to be defined:

`HomotopyContinuation.degrees`

— Method.`degrees(F::AbstractSystem)`

Returns a the degrees of the polynomials.

### Optional

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

.

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

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