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 — TypeFPSystem(polynomials, vars) <: AbstractSystemCreate a polynomial system using the FixedPolynomials package.
HomotopyContinuation.SPSystem — TypeSPSystem(polynomials, vars) <: AbstractSystemCreate 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 — TypeFixedHomotopy(H, t) <: AbstractSystemFix a homotopy H(x,t) at t
HomotopyContinuation.FixedParameterSystem — TypeFixedParameterSystem(F, p) <: AbstractSystemFix a parametrized system F(x; p) at p, i.e., it is treated as a system without parameters.
HomotopyContinuation.CompositionSystem — TypeCompositionSystem(composition::Composition, systems_constructor) <: AbstractSystemA 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 — TypeAbstractSystemRepresenting a system of polynomials.
HomotopyContinuation.AbstractSystemCache — TypeAbstractSystemCacheA cache to avoid allocations for the evaluation of an AbstractSystem.
HomotopyContinuation.SystemNullCache — TypeSystemNullCacheAn empty cache if no cache is necessary.
Mandatory
The following methods are mandatory to implement.
HomotopyContinuation.cache — Methodcache(F::AbstractSystem, x)::AbstractSystemCacheCreate a cache for the evaluation (incl. Jacobian) of F with elements of the type of x.
cache(F::AbstractSystem, x, p)::AbstractSystemCacheCreate a cache for the evaluation (incl. Jacobian) of F with elements of the type of x and parameters p.
HomotopyContinuation.evaluate! — Methodevaluate!(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 — Functionevaluate(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! — Methodjacobian!(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 — Functionjacobian(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 — MethodBase.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! — Functiondifferentiate_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 — Functiondifferentiate_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 — Methoddegrees(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.
HomotopyContinuation.evaluate_and_jacobian! — Methodevaluate_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! — Methodevaluate_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).