Certification (experimentell)
We provide experimentell support for certifying non-singular solutions to polynomial systems.
HomotopyContinuation.certify — Functioncertify(F, solutions, [p, certify_cache]; options...)
certify(F, result, [p, certify_cache]; options...)Attempt to certify that the given approximate solutions correspond to true solutions of the polynomial system $F(x;p)$. The system $F$ has to be an (affine) square polynomial system. Also attemps to certify for each solutions whether it approximates a real solution. The certification is done using interval arithmetic and the Krawczyk method[Moo77]. Returns a CertificationResult which additionall returns the number of distinct solutions. For more details of the implementation see [BRT20].
Options
show_progress = true: Iftrueshows a progress bar of the certification process.compile = true: See thesolvedocumentation.
Example
We take the first example from our introduction guide.
@var x y
# define the polynomials
f₁ = (x^4 + y^4 - 1) * (x^2 + y^2 - 2) + x^5 * y
f₂ = x^2+2x*y^2 - 2y^2 - 1/2
F = System([f₁, f₂], variables = [x,y])
result = solve(F)Result with 18 solutions
========================
• 18 paths tracked
• 18 non-singular solutions (4 real)
• random seed: 0xcaa483cd
• start_system: :polyhedralWe see that we obtain 18 solutions and it seems that 4 solutions are real. However, this is based on heuristics. To be absolute certain we can certify the result
certify(F, result)CertificationResult
===================
• 18 solutions given
• 18 certified solutions (4 real)
• 18 distinct certified solutions (4 real)and see that there are indeed 18 solutions and that they are all distinct.
HomotopyContinuation.SolutionCertificate — TypeSolutionCertificateResult of certify for a single solution. Contains the initial solutions and if the certification was successfull a vector of complex intervals where the true solution is contained in.
HomotopyContinuation.initial_solution — Functioninitial_solution(C::SolutionCertificate)Returns the given initial solution.
HomotopyContinuation.certified_solution — Functioncertified_solution(C::SolutionCertificate)Returns a vector of complex intervals where the true solution is contained in.
HomotopyContinuation.is_certified — Functionis_certified(C::SolutionCertificate)Returns true if C certifies that the given initial solution corresponds to a true solution.
HomotopyContinuation.is_real — Methodis_real(C::SolutionCertificate)Returns true if C certifies that the given initial solution corresponds to a true real solution of the system.
HomotopyContinuation.is_positive — Methodis_positive(C::SolutionCertificate)Returns true if C is certifiably a real, positive solution.
HomotopyContinuation.CertificationResult — TypeCertificationResultThe result of certify for multiple solutions. Contains a vector of SolutionCertificate as well as a list of certificates which correspond to the same true solution.
HomotopyContinuation.certificates — Functioncertificates(R::CertificationResult)Obtain the stored SolutionCertificates.
HomotopyContinuation.ncertified — Functionncertified(R::CertificationResult)Returns the number of certified solutions.
HomotopyContinuation.nreal_certified — Functionnreal_certified(R::CertificationResult)Returns the number of certified real solutions.
HomotopyContinuation.ndistinct_certified — Functionndistinct_certified(R::CertificationResult)Returns the number of distinct certified solutions.
HomotopyContinuation.ndistinct_real_certified — Functionndistinct_real_certified(R::CertificationResult)Returns the number of distinct certified real solutions.
HomotopyContinuation.save — Methodsave(filename, C::CertificationResult)Store a text representation of the certification result C on disk.