MixedSubdivisions

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.

MixedSubdivisions.MixedCellIterator — Type.
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.