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

`1`

- 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 Binomial*system*data from an input polynomial system. Binomial systems obtained from the mixed cells induced by the $Log|C|$-lifting. The object Binomial*system*data contains the binomial system, normal vectors, lifting vectors, and cells from the mixed subdivision computed. The object Binomial*system*data 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)`