Positive Dimensional Solution Sets

The basic data structure to work with positive dimensional solution sets $V(F)$ of a polynomial system $F$ is a WitnessSet $W$. The general idea is to intersect $V(F)$ with an (affine) linear space $L$ such that the intersection $V(F) ∩ L$ consists of only finitely many points (witnesses).

To compute a WitnessSet call witness_set.

HomotopyContinuation.witness_setFunction
witness_set(F; codim = nvariables(F) - length(F), dim = nothing, options...)

Compute a WitnessSet for F in the given dimension (resp. codimension) by sampling a random (affine) linear subspace. After constructing the system this calls solve with the provided options.

witness_set(F, L; options...)

Compute WitnessSet for F and the (affine) linear subspace L.

witness_set(W::WitnessSet, L; options...)

Compute a new WitnessSet with the (affine) linear subspace L by moving the linear subspace stored in W to L.

Example

julia> @var x y;
julia> F = System([x^2 + y^2 - 5], [x, y])
System of length 1
 2 variables: x, y

 -5 + x^2 + y^2

julia> W = witness_set(F)
Witness set for dimension 1 of degree 2
source

To compute witness sets for all possible dimensions use regeneration or witness_sets.

HomotopyContinuation.regenerationFunction
regeneration(F::System; options...)

This solves $F=0$ equation-by-equations and returns a WitnessSet for every dimension without decomposing them into irreducible components (witness sets that are not decomposed are also called witness supersets).

The implementation is based on the algorithm u-regeneration by Duff, Leykin and Rodriguez.

Options

  • show_progress = true: indicate whether the progress of the computation should be displayed.
  • sorted = true: the polynomials in F will be sorted by degree in decreasing order.
  • endgame_options: EndgameOptions for the EndgameTracker.
  • tracker_options: TrackerOptions for the Tracker.
  • seed: choose the random seed.

Example

The following example computes witness sets for a union of two circles.

julia> @var x y
julia> f = (x^2 + y^2 - 1) * ((x-1)^2 + (y-1)^2 - 1)
julia> W = regeneration([f])
1-element Vector{WitnessSet}:
    Witness set for dimension 1 of degree 4  
source

Witness sets can be decomposed into irreducible components by using the decompose function.

HomotopyContinuation.decomposeFunction
decompose(Ws::Vector{WitnessPoints}; options...)

This function decomposes a WitnessSet or a vector of WitnessSet into irreducible components.

Options

  • show_progress = true: indicate whether the progress of the computation should be displayed.
  • show_monodromy_progress = false: indicate whether the progress of the monodromy computation should be displayed.
  • monodromy_options: MonodromyOptions for monodromy_solve.
  • max_iters = 50: maximal number of iterations for the decomposition step.
  • warning = true: if true prints a warning when the trace_test fails.
  • threading = true: enables multiple threads.
  • seed: choose the random seed.

Example

The following example decomposes the witness set for a union of two circles.

julia> @var x y
julia> f = (x^2 + y^2 - 1) * ((x-1)^2 + (y-1)^2 - 1)
julia> W = regeneration([f])
julia> decompose(W)
Numerical irreducible decomposition with 2 components
• 2 component(s) of dimension 1.

 degree table of components:
╭───────────┬───────────────────────╮
│ dimension │ degrees of components │
├───────────┼───────────────────────┤
│     1     │        (2, 2)         │
╰───────────┴───────────────────────╯
source

Numerical Irreducible Decomposition

A numerical irreducible decomposition for $F$ is a collection of witness sets $W₁, ..., Wᵣ$ such that the $Wᵢ$ are all witness sets for different irreducible components and $V(F)$ is their union.

HomotopyContinuation.numerical_irreducible_decompositionFunction
numerical_irreducible_decomposition(F::System; options...)

Computes the numerical irreducible of the variety defined by $F=0$.

Options

  • show_progress = true: indicate whether the progress of the computation should be displayed.
  • show_monodromy_progress = false: indicate whether the progress of the monodromy computation should be displayed.
  • sorted = true: the polynomials in F will be sorted by degree in decreasing order.
  • endgame_options: EndgameOptions for the EndgameTracker.
  • tracker_options: TrackerOptions for the Tracker.
  • monodromy_options: MonodromyOptions for monodromy_solve.
  • max_iters = 50: maximal number of iterations for the decomposition step.
  • warning = true: if true prints a warning when the trace_test fails.
  • threading = true: enables multiple threads.
  • seed: choose the random seed.

Example

The following example computes witness sets for a union of one 2-dimensional component of degree 2, two 1-dimensional components each of degree 4 and 8 points.

julia> @var x, y, z
julia> p = (x * y - x^2) + 1 - z
julia> q = x^4 + x^2 - y - 1
julia> F = [p * q * (x - 3) * (x - 5);
            p * q * (y - 3) * (y - 5);
            p * (z - 3) * (z - 5)]

julia> N = numerical_irreducible_decomposition(F)
Numerical irreducible decomposition with 4 components
• 1 component(s) of dimension 2.
• 2 component(s) of dimension 1.
• 1 component(s) of dimension 0.

 degree table of components:
╭───────────┬───────────────────────╮
│ dimension │ degrees of components │
├───────────┼───────────────────────┤
│     2     │           2           │
│     1     │        (4, 4)         │
│     0     │           8           │
╰───────────┴───────────────────────╯
source
HomotopyContinuation.nidFunction
nid(F::System; options...)

Calls numerical_irreducible_decomposition.

Example

julia> @var x, y
julia> f = [x^2 + y^2 - 1]
julia> N = nid(f)

Numerical irreducible decomposition with 1 components
• 1 component(s) of dimension 1.

 degree table of components:
╭───────────┬───────────────────────╮
│ dimension │ degrees of components │
├───────────┼───────────────────────┤
│     1     │           2           │
╰───────────┴───────────────────────╯
source

The output of nid is a NumericalIrreducibleDecomposition.

HomotopyContinuation.ncomponentsFunction
ncomponents(N::NumericalIrreducibleDecomposition;
    dims::Union{Vector{Int},Nothing} = nothing)

Returns the total number of components in N. dims specifies the dimensions that should be considered.

source
HomotopyContinuation.witness_setsFunction
witness_sets(N::NumericalIrreducibleDecomposition;
    dims::Union{Vector{Int},Nothing} = nothing)

Returns the witness sets in N. dims specifies the dimensions that should be considered.

source
HomotopyContinuation.ModelKit.degreesFunction
degrees(f::AbstractVector{Expression}, vars = variables(f); expanded = false)

Compute the degrees of the expressions f in vars. Unless expanded is true the expressions are first expanded.

source
degrees(F::System)

Return the degrees of the given system.

source
degrees(N::NumericalIrreducibleDecomposition;
    dims::Union{Vector{Int},Nothing} = nothing)

Returns the degrees of the components in N. dims specifies the dimensions that should be considered.

source

Computing Information about Witness Sets

To obtain information about a WitnessSet the following functions are provided.

To test for completeness of a WitnessSet you can perform a trace_test

HomotopyContinuation.trace_testFunction
trace_test(W::WitnessSet; options...)

Performs a trace test [LRS18] to verify whether the given witness set W is complete. Returns the trace of the witness set which should be theoretically be 0 if W is complete. Due to floating point arithmetic this is not the case, thus is has to be manually checked that the trace is sufficiently small. Returns nothing if the trace test failed due to path tracking failures. The options are the same as for calls to witness_set.

julia> @var x y;
julia> F = System([x^2 + y^2 - 5], [x, y])
System of length 1
 2 variables: x, y

 -5 + x^2 + y^2

julia> W = witness_set(F)
Witness set for dimension 1 of degree 2

julia> trace = trace_test(W)
9.981960497718987e-16

APA

source
  • LRS18Leykin, Anton, Jose Israel Rodriguez, and Frank Sottile. "Trace test." Arnold Mathematical Journal 4.1 (2018): 113-125.