RealPolyhedralHomotopy.jl

RealPolyhedralHomotopy.jl is a package for finding real roots of systems of polynomial equations using polyhedral homotopy. The package implements the algorithm for the real polyhedral homotopy establised in A Polyhedral Homotopy Algorithm For Real Zeros. The idea for the real polyhedral homotopy motivated from the celebrated article A Polyhedral Method for Solving Sparse Polynomial Systems to apply the polyhedral homotopy method for real roots finding.

The authors of this package are

Installation

The package can be installed via the Julia package manager. It is suggested to use Julia 1.6.1 or higher.

pkg> add RealPolyhedralHomotopy

Introduction

We support system input through the HomotopyContinuation package.

using RealPolyhedralHomotopy

@var x y;
F = System([-1 - 24000*y + x^3, -9 + 50*x*y - 1*y^2]);

For finding real roots, the list of binomial systems corresponding to F is required as a start system.

B = generate_binomials(F);

Binomial_system_data

B.binomial_system

2-element Vector{Any}:
 Expression[-24000*y + x^3, 50*x*y - y^2]
 Expression[-24000*y + x^3, -9 + 50*x*y]

Using the function rph_track, real roots are found by tracking the real polyhedral homotopy.

@var x y;
F = System([-1 - 24000*y + x^3, -9 + 50*x*y - 1*y^2]);
B = generate_binomials(F);
realSols = rph_track(B,F)

4-element Vector{Vector{Float64}}:
 [-1095.4451129504978, -54772.25548320812]
 [1095.4451137838312, 54772.255524874796]
 [8.111114476617955, 0.02219298606763958]
 [-8.103507635567631, -0.02221382112196499]

Functions for the real polyhedral homotopy

RealPolyhedralHomotopy.certify_patchwork — Function

certify_patchwork(F::System; Number_Real_Solutions = false)

Certify if a given system is patchworked that all real solutions can be found using the real polyhedral homotopy. It returns the value 1 if the system F is certified to be patchworked according to the certification inequality. Otherwise, 0 is returned.

Arguments

F : The target system for the real polyhedral homotopy.

@var x y;
F = System([-1 - 24000*y + x^3, -9 + 50*x*y - 1*y^2]);
result = certify_patchwork(F)

There is an option Number_Real_Solutions returning (1,k) where k is number of real solutions to the target system when the target system is patchedworked. The default value for the option is false.

result = certify_patchwork(F; Number_Real_Solutions = true)

(1,4)

RealPolyhedralHomotopy.generate_binomials — Function

generate_binomials(F::System)

Return a wrapper object Binomialsystemdata from an input polynomial system. Binomial systems obtained from the mixed cells induced by the $Log|C|$-lifting. The object Binomialsystemdata contains the binomial system, normal vectors, lifting vectors, and cells from the mixed subdivision computed. The object Binomialsystemdata is used as an input for the rph_track function.

Arguments

F : The target system for the real polyhedral homotopy.

B = generate_binomials(F)

Binomial_system_data

B.binomial_system

2-element Vector{Any}:
 Expression[-24000*y + x^3, 50*x*y - y^2]
 Expression[-24000*y + x^3, -9 + 50*x*y]

RealPolyhedralHomotopy.rph_track — Function

rph_track(B::Binomial_system_data, F::System; Certification = false)

Return the output of tracking the real solutions of a given list of binomial systems to the target system.

Arguments

B : The object Binomial_system_data obtained from generate_binomials(F).
F : The target system for the real polyhedral homotopy.

@var x y;
F = System([-1 - 24000*y + x^3, -9 + 50*x*y - 1*y^2]);
B = generate_binomials(F);
realSols = rph_track(B,F)

4-element Vector{Vector{Float64}}:
 [-1095.4451129504978, -54772.25548320812]
 [1095.4451137838312, 54772.255524874796]
 [8.111114476617955, 0.02219298606763958]
 [-8.103507635567631, -0.02221382112196499]

The optional argument Certification certifies that all real solutions to a patchedworked system are found.

This is done by an a posteriori certification for numerical approximations obtained by the real polyhedral homotopy. When the real polyhedral homotopy root-finding is certified, it returns a list of solutions to the target and 1; otherwise, it returns 0. The default value for the option is false.

realSols = rph_track(B,F; Certification = true)

([[-1095.4451129504978, -54772.25548320812], [1095.4451137838312, 54772.255524874796], [8.111114476617955, 0.02219298606763958], [-8.103507635567631, -0.022213821121964985]], 1)