Witness Sets
A WitnessSet
$W$ is the basic data structure to work with positive dimensional solution sets $V(F)$ of a polynomial system $F$. 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). Over the complex numbers the number of points is independent of the linear space $L$ and called the degree of $V(F)$.
HomotopyContinuation.WitnessSet
— TypeWitnessSet(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
— Functionwitness_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 obtain information about a WitnessSet
the following functions are provided.
HomotopyContinuation.solutions
— Methodsolutions(W::WitnessSet)
Get the solutions stored in W
.
HomotopyContinuation.results
— Methodresults(W::WitnessSet)
Get the results stored in W
.
HomotopyContinuation.system
— Functionsystem(W::WitnessSet)
Get the system stored in W
.
HomotopyContinuation.linear_subspace
— Functionlinear_subspace(W::WitnessSet)
Get the linear subspace stored in W
.
HomotopyContinuation.dim
— Methoddim(W::WitnessSet)
The dimension of the algebraic set encoded by the witness set.
HomotopyContinuation.codim
— Methodcodim(W::WitnessSet)
The dimension of the algebraic set encoded by the witness set.
MultivariatePolynomials.degree
— Methoddegree(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
— Functiontrace_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.