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

`HomotopyContinuation.WitnessSet`

— Type`WitnessSet(F, L, S)`

Store solutions `S`

of the polynomial system `F(x) = L(x) = 0`

into a witness set.

To compute a `WitnessSet`

call `witness_set`

.

`HomotopyContinuation.witness_set`

— Function`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
```

To compute witness sets for all possible dimensions use `regeneration`

or `witness_sets`

.

`HomotopyContinuation.regeneration`

— Function`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
```

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

function.

`HomotopyContinuation.decompose`

— Function`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

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_decomposition`

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

`HomotopyContinuation.nid`

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

The output of `nid`

is a `NumericalIrreducibleDecomposition`

.

`HomotopyContinuation.NumericalIrreducibleDecomposition`

— Type`NumericalIrreducibleDecomposition`

Store the witness sets in a common data structure.

`HomotopyContinuation.n_components`

— Function```
n_components(N::NumericalIrreducibleDecomposition;
dims::Union{Vector{Int},Nothing} = nothing)
```

Returns the total number of components in `N`

. `dims`

specifies the dimensions that should be considered.

`HomotopyContinuation.witness_sets`

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

Returns the witness sets in `N`

. `dims`

specifies the dimensions that should be considered.

`HomotopyContinuation.ModelKit.degrees`

— Function`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.

## Computing Information about Witness Sets

To obtain information about a `WitnessSet`

the following functions are provided.

`HomotopyContinuation.solutions`

— Method`solutions(W::WitnessSet)`

Get the solutions stored in `W`

.

`HomotopyContinuation.results`

— Method`results(W::WitnessSet)`

Get the results stored in `W`

.

`HomotopyContinuation.system`

— Function`system(W::WitnessSet)`

Get the system stored in `W`

.

`HomotopyContinuation.linear_subspace`

— Function`linear_subspace(W::WitnessSet)`

Get the linear subspace stored in `W`

.

`HomotopyContinuation.dim`

— Method`dim(W::WitnessSet)`

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

`HomotopyContinuation.codim`

— Method`codim(W::WitnessSet)`

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

`MultivariatePolynomials.degree`

— Method`degree(W::WitnessSet)`

Returns the degree of the witness set `W`

. This equals the number of solutions stored.

To test for completeness of a `WitnessSet`

you can perform a `trace_test`

`HomotopyContinuation.trace_test`

— Function`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

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