Positive Dimensional Solution Sets

WitnessSet(F, L, S)

Store solutions S of the polynomial system F(x) = L(x) = 0 into a witness set.

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

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  

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)         │
╰───────────┴───────────────────────╯

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           │
╰───────────┴───────────────────────╯

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           │
╰───────────┴───────────────────────╯

NumericalIrreducibleDecomposition

Store the witness sets in a common data structure.

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.

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

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

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.

degrees(F::System)

Return the degrees of the given system.

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.

solutions(W::WitnessSet)

Get the solutions stored in W.

results(W::WitnessSet)

Get the results stored in W.

system(W::WitnessSet)

Get the system stored in W.

linear_subspace(W::WitnessSet)

Get the linear subspace stored in W.

dim(W::WitnessSet)

The dimension of the algebraic set encoded by the witness set.

codim(W::WitnessSet)

The dimension of the algebraic set encoded by the witness set.

degree(W::WitnessSet)

Returns the degree of the witness set W. This equals the number of solutions stored.

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