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

is_irreducible(W::WitnessSet)

Return true, if it was computed that W is irreducible, false if it was computed that W is not irreducible, and :undecided otherwise.

Example

julia> @var x[1:2]
julia> f = System([sum(x.^2) - 1])
julia> W = witness_set(f; dim = 1);
julia> is_irreducible(W)
:undecided

julia> dec = decompose(W);
julia> W_irred = first(dec);
julia> is_irreducible(W_irred)
true
end

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

• sorted = true: if true, the polynomials in F will be sorted by degree in decreasing order.
• max_codim: the maximal codimension until which witness supersets should be computed.
• show_progress = true: indicate whether a progress bar should be displayed.
• show_monodromy_progress = false: indicate whether the progress bar of monodromy_solve should be displayed.
• tracker_options: TrackerOptions for the Tracker.
• endgame_options: EndgameOptions for the EndgameTracker.
• monodromy_options: MonodromyOptions for monodromy_solve.
• atol = 1e-14 and rtol = sqrt(eps()): a point y is considered equal to x when the distance between xand y is smaller than max(atol, norm(x, Inf) * rtol).
• threading = true: Enable multi-threading for the computation. The number of available threads is controlled by the environment variable JULIA_NUM_THREADS. You can run Julia with n threads using the command julia -t n; e.g., julia -t 8 for n=8. (Some CPUs hang when using multiple threads. To avoid this run Julia with 1 interactive thread for the REPL; e.g., julia -t 8,1 for n=8. Note that some CPUs seem to let Julia crash when using that option.)
• 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 a progress bar should be displayed.
• show_monodromy_progress = false: indicate whether the progress bar of monodromy_solve 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: Enable multi-threading for the computation. The number of available threads is controlled by the environment variable JULIA_NUM_THREADS. You can run Julia with n threads using the command julia -t n; e.g., julia -t 8 for n=8. (Some CPUs hang when using multiple threads. To avoid this run Julia with 1 interactive thread for the REPL; e.g., julia -t 8,1 for n=8. Note that some CPUs seem to let Julia crash when using that option.)
• 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> dec = decompose(W)
2-element Vector{WitnessSet}:
 Witness set for dimension 1 of degree 2
 Witness set for dimension 1 of degree 2

The decomposition can be stored in a NumericalIrreducibleDecomposition data structure.

julia> N = NumericalIrreducibleDecomposition(dec)
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 a progress bar should be displayed.
• sorted = true: the polynomials in F will be sorted by degree in decreasing order.
• max_codim: the maximal codimension until which witness supersets should be computed.
• endgame_options: EndgameOptions for the EndgameTracker.
• tracker_options: TrackerOptions for the Tracker.
• monodromy_options_for_regeneration: MonodromyOptions for monodromy_solve in regeneration.
• monodromy_options_for_decompose: MonodromyOptions for monodromy_solve in decompose.
• show_progresss = false: if true, sets show_monodromy_for_regeneration_progress and show_monodromy_for_decompose_progress to true.
• show_monodromy_for_regeneration_progress = false: indicate whether the progress bar of monodromy_solve in regeneration should be displayed.
• show_monodromy_for_decompose_progress = false: indicate whether the progress bar of monodromy_solve in decompose should be displayed.
• max_iters = 50: maximal number of iterations for the decomposition step.
• atol = 1e-14 and rtol = sqrt(eps()): a point y is considered equal to x when the distance between xand y is smaller than max(atol, norm(x, Inf) * rtol). This option is used for regeneration.
• warning = true: if true prints a warning when the trace_test fails.
• threading = true: Enable multi-threading for the computation. The number of available threads is controlled by the environment variable JULIA_NUM_THREADS. You can run Julia with n threads using the command julia -t n; e.g., julia -t 8 for n=8. (Some CPUs hang when using multiple threads. To avoid this run Julia with 1 interactive thread for the REPL; e.g., julia -t 8,1 for n=8. Note that some CPUs seem to let Julia crash when using that option.)
• 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 11 components
======================================================
• 1 component(s) of dimension 2.
• 2 component(s) of dimension 1.
• 8 component(s) of dimension 0.

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

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 component
====================================================
• 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