# Introduction

MixedSubdivisions.jl is package for computing a (fine) mixed subdivision and the mixed volume of lattice polytopes. The mixed volume of lattice polytopes arising as Newton polytopes of a polynomial system gives an upper bound of the number of solutions of the system. This is the celebrated BKK-Theorem. A (fine) mixed subdivision can be used to efficiently solve sparse polynomial systems as first described in A Polyhedral Method for Solving Sparse Polynomial Systems by Huber and Sturmfels.

There are many algorithms for computing mixed volumes and mixed subdivisions. This implementation is based on the tropical homotopy continuation algorithm by Anders Jensen described in arXiv:1601.02818.

## Installation

The package can be installed via the Julia package manager

`pkg> add MixedSubdivisions`

## Short introduction

We support polynomial input through the DynamicPolynomials package.

```
@polyvar x y;
# create two polynomials
f = y^2 + x * y + x + 1;
g = x^2 + x * y + y + 1;
# mixed volume
mixed_volume([f, g])
```

`4`

Alternatively we could also give directly the supports to `mixed_volume`

.

`A = support([f, g])`

```
2-element Array{Array{Int32,2},1}:
[1 0 1 0; 1 2 0 0]
[2 1 0 0; 0 1 1 0]
```

`mixed_volume(A)`

`4`

Now let's compute the mixed cells with respect to a given lift.

```
w₁ = [2, 0, 0, 0];
w₂ = [8, 4, 3, 0];
mixed_cells(A, [w₁, w₂])
```

```
2-element Array{MixedCell,1}:
MixedCell:
• volume → 3
• indices → Tuple{Int64,Int64}[(2, 3), (4, 2)]
• normal → [-2.66667, -1.33333]
• is_fine → true
MixedCell:
• volume → 1
• indices → Tuple{Int64,Int64}[(3, 1), (1, 2)]
• normal → [-6.0, -2.0]
• is_fine → true
```

Now let's compare that to another lift.

```
v₁ = [1, 0, 0, 0];
v₂ = [8, 4, 3, 0];
mixed_cells(A, [v₁, v₂])
```

```
3-element Array{MixedCell,1}:
MixedCell:
• volume → 2
• indices → Tuple{Int64,Int64}[(2, 1), (4, 2)]
• normal → [-2.5, -1.5]
• is_fine → true
MixedCell:
• volume → 1
• indices → Tuple{Int64,Int64}[(3, 1), (2, 4)]
• normal → [-3.0, -1.0]
• is_fine → true
MixedCell:
• volume → 1
• indices → Tuple{Int64,Int64}[(3, 1), (1, 2)]
• normal → [-5.0, -1.0]
• is_fine → true
```

If you don't want to wait until all mixed cells got computed you can also use the `MixedCellIterator`

```
for cell in MixedCellIterator(A, [v₁, v₂])
println(cell)
end
```

```
MixedCell:
• volume → 2
• indices → Tuple{Int64,Int64}[(2, 1), (4, 2)]
• normal → [-2.5, -1.5]
• is_fine → true
MixedCell:
• volume → 1
• indices → Tuple{Int64,Int64}[(3, 1), (2, 4)]
• normal → [-3.0, -1.0]
• is_fine → true
MixedCell:
• volume → 1
• indices → Tuple{Int64,Int64}[(3, 1), (1, 2)]
• normal → [-5.0, -1.0]
• is_fine → true
```

Also if you just want to generate a random lift such that a fine mixed subdivision is obtained you can use the `fine_mixed_cells`

function.

```
cells, lift = fine_mixed_cells(A);
cells
```

```
2-element Array{MixedCell,1}:
MixedCell:
• volume → 2
• indices → Tuple{Int64,Int64}[(2, 1), (4, 1)]
• normal → [-1762.5, -894.5]
• is_fine → true
• β → [-3674.0, -1517.0]
MixedCell:
• volume → 2
• indices → Tuple{Int64,Int64}[(3, 1), (1, 4)]
• normal → [-1762.5, 568.0]
• is_fine → true
• β → [-2211.5, -1517.0]
```

`lift`

```
2-element Array{Array{Int32,1},1}:
[-1017, -1885, -449, -1914]
[2008, 1735, 538, -1517]
```

## API

`MixedSubdivisions.mixed_volume`

— Function.```
mixed_volume(F::Vector{<:MP.AbstractPolynomialLike}; show_progress=true, algorithm=:regeneration)
mixed_volume(𝑨::Vector{<:Matrix}; show_progress=true, algorithm=:regeneration)
```

Compute the mixed volume of the given polynomial system `F`

resp. represented by the support `𝑨`

. There are two possible values for `algorithm`

:

`:total_degree`

: Use the total degree homotopy algorithm described in Section 7.1`:regeneration`

: Use the tropical regeneration algorithm described in Section 7.2

`MixedSubdivisions.mixed_cells`

— Function.`mixed_cells(support::Vector{<:Matrix}, lifting::Vector{<:Vector})`

Compute all (fine) mixed cells of the given `support`

induced by the given `lifting`

. If the lifting is not sufficiently generic the mixed cells induced by a sligtly perturbated lifting are computed. The mixed cells are stored as a `MixedCell`

.

`MixedSubdivisions.fine_mixed_cells`

— Function.```
fine_mixed_cells(f::Vector{<:MP.AbstractPolynomialLike}; show_progress=true)
fine_mixed_cells(support::Vector{<:Matrix}; show_progress=true)
```

Compute all (fine) mixed cells of the given `support`

induced by a generic lifting. This guarantees that all induce intial forms binomials. Returns a `Vector`

of all mixed cells and the corresponding lifting or `nothing`

if the algorithm wasn't able to compute fine mixed cells. This can happen due to some current technical limitations.

`MixedSubdivisions.MixedCell`

— Type.`MixedCell`

Data structure representing a (fine) mixed cell.

**Fields**

`indices::Vector{NTuple{2, Int}}`

: The columns of the support creating the mixed cell.`normal::Vector{Float64}`

: The inner normal vector of the lifted mixed cell.`β::Vector{Float64}`

: The vector $(\min_{a \in A_i} ⟨a,γ⟩)_i$ where $γ$ is`normal`

.`volume::Int`

: The volume of the mixed cell.

`MixedSubdivisions.volume`

— Function.`volume(C::MixedCell)`

Returns the volume of the mixed cell `C`

.

`MixedSubdivisions.normal`

— Function.`normal(C::MixedCell)`

The inner normal vector of the lifted mixed cell.

`MixedSubdivisions.indices`

— Function.`indices(C::MixedCell)`

Returns the indices of the support creating the mixed cell.

`MixedSubdivisions.is_fine`

— Function.`is_fine(cell::MixedCell)`

Checks whether for a given mixed cell `cell`

whether this is a fine mixed cell.

`MixedCellIterator(support:Vector{<:Matrix}, lifting::Vector{<:Vector{<:Integer}})`

Returns an iterator over all (fine) mixed cells of the given `support`

induced by the given `lifting`

. If the lifting is not sufficiently generic the mixed cells induced by a sligtly perturbated lifting are computed. The iterator returns in each iteration a `MixedCell`

. Note that due to efficiency reason the same object is returned in each iteration, i.e., if you want to store the computed cells you need to make a `copy`

. Alternatively you can also use `mixed_cells`

to compute all mixed cells.

`MixedSubdivisions.support`

— Function.`support(F::Vector{<:MP.AbstractPolynomialLike}, vars=MP.variables(F), T::Type{<:Integer}=Int32)`

Compute the support of the polynomial system `F`

with the given variables `vars`

. The returned matrices have element type `T`

.